[C] 게리맨더링 2

백준 17779번

 

별찍기 응용 느낌ㅋㅋㅋ

 

#include <stdio.h>
 
int map[25][25];
int arr[25][25];
int N,ans=1000000;
 
void printMap(){
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= N ; j++) printf("%d ",arr[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
void getMinMax(){
    int sum[6] = {0,};
    int min = 10000000;
    int max = 0;
    for(int i = 1; i <= N ; i++){
        for(int j = 1; j <= N ; j++){
            sum[arr[i][j]] += map[i][j];
        }
    }
    for(int i = 1 ; i <= 5 ; i++){
        if(max<sum[i]) max = sum[i];
        if(min>sum[i]) min = sum[i];
    }
    if(ans>max-min) ans = max-min;
}
 
int main(){
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= N ; j++) scanf("%d",&map[i][j]);
    }
 
    for(int d1 = 1 ; d1 <= N ; d1++){
        for(int d2 = 1 ; d2<=N ; d2++){
            for(int x = 1 ; x <= N - (d1+d2) ; x++){
                for(int y = 1+d1 ; y <= N - d2 ; y++){
 
                    // 1
                    for(int r = 1 ; r < x+d1 ; r++){
                        for(int c = 1 ; c <= y ; c++){
                            arr[r][c] = 1;
                        }
                    }
 
                    // 2
                    for(int r = 1 ; r <= x+d2 ; r++){
                        for(int c = y+1 ; c <= N ; c++){
                            arr[r][c] = 2;
                        }
                    }
 
                    // 3 
                    for(int r = x+d1 ; r <= N ; r++){
                        for(int c = 1 ; c < y-d1+d2 ; c++){
                            arr[r][c] = 3;
                        }
                    }
 
                    // 4
                    for(int r = x+d2+1 ; r<=N ; r++){
                        for(int c = y-d1+d2 ; c <= N ; c++){
                            arr[r][c] = 4;
                        }
                    }
 
                    // 5
                    for(int r = x ; r <= x+d1 ;r++){
                        for(int i = 0 ; i < r-x+1 ; i++){
                            arr[r][y-i] = 5;
                        }
                    }
 
                    for(int r = x ; r <= x+d2 ; r++){
                        for(int i = 0 ; i < r-x+1 ; i++){
                            arr[r][y+i] = 5;
                        }
                    }
 
                    for(int r = x+d1+d2 ; r >= x+d1 ; r--){
                        for(int i = 0 ; i < x+d1+d2-r+1 ; i++){
                            arr[r][y-d1+d2-i] = 5;
                        }
                    }
 
                    for(int r = x+d1+d2 ; r >= x+d2 ; r--){
                        for(int i = 0 ; i < x+d1+d2-r+1 ; i++){
                            arr[r][y-d1+d2+i] = 5;
                        }
                    }
 
 
                    // printf("%d %d %d %d\n",d1,d2,x,y);
                    // printMap();
                    getMinMax();
                }
            }
        }
    }
    printf("%d\n",ans);
}

 

 

이렇게 먼저 1,2,3,4를 쉽게 칠해준 후

5만 구역에 맞춰서 다시 칠해줬다

 

5 구역 칠해주는 방법은 제일 기본 별찍기인 하나부터 시작해서 밑으로 내려갈수록 별 개수가 늘어나는 방법을 그대로 사용했다

헷갈릴것도 없고 좋았던 문제

이정도로만 코테 나오면 좋겠다..ㅎㅎ