BOJ 17779

23 Apr 2020 • ProblemSolving

게리맨더링 2

문제출처

문제 해석

  • 5개의 선거구로 나누어서 인구가 가장 많은 선거구와 가장 적은 선거구의 차이의 최솟값을 구하는 문제입니다.
  • 먼저 기준점(x,y)와 길이 d1,d2를 정합니다.
  • 선거구의 경계는 다음과 같습니다.
    1. (x,y),(x+1,y-1),…,(x+d1,y-d1)
    2. (x,y),(x+1,y+1),…,(x+d1,y+d2)
    3. (x+d1,y-d1),(x+d1+1,y-d1+1)…(x+d1+d2,y-d1+d2)
    4. (x+d2,y+d2),(x+d2+1,y+d201),…,(d+d2+d1,y+d2-d1)
  • 위의 경계선과 경계선 안의 범위는 모두 5번 선거구입니다.
  • 나머지 구역은 다음 기준을 따라서 결정됩니다.
    1. 1<=r < x+ d1, 1<=c <=y
    2. 1<=r <= x+d1, y< c <=N
    3. x+d1 <= r <= N, 1<= c < y-d1+d2
    4. x+d2 < r <=N, y-d1+d2 <=c <=N

설계(20)

  • 완전탐색문제입니다.
  • 먼저 x,y,d1,d2를 정합니다.
  • 그 후, 선거구를 정합니다.
  • 선거구를 정할 때, 모든 좌표를 5로 초기화한 후 시작합니다.
  • 주어지는 조건에 따라서 선거구를 정하고, 각 선거구의 인구수를 모두 더해줍니다.

구현(50)

코드
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 21
#define INF 987654321
int map[MAXN][MAXN];
int tmp_arr[MAXN][MAXN];
int num[6];
int N;
int ans = INF;
int go(int x, int y, int d1, int d2){
    memset(tmp_arr,0,sizeof(tmp_arr));
    memset(num,0,sizeof(num));
    int max_num = 0;
    int min_num = INF;
    for (int i =1 ; i <=N; i++){
        for (int j= 1 ;j<=N; j++){
            tmp_arr[i][j] = 5;
        }
    }
    // 1번 선거구
    int cnt = 0;
    for (int i = 1; i< x+d1; i++){
        if (i>=x) cnt++;
        for (int j = 1; j <= y-cnt; j++){
            tmp_arr[i][j] = 1;
        }
    }
    // 2번 선거구
    cnt = 0;
    for (int i = 1; i<= x+d2; i++){
        if (i>x) cnt++;
        for (int j =y+cnt+1; j <= N; j++){
            tmp_arr[i][j] = 2;
        }
    }
    // 3번 선거구
    cnt = -1;
    for (int i = x+d1; i<=N; i++){
        if (i <= x+d1+d2) cnt++;
        for (int j = 1; j <=y-d1+cnt-1; j++){
            tmp_arr[i][j] = 3;
        }
    }
    // 4번 선거구
    cnt = -1;
    for (int i = x+d2+1; i<=N;i++){
        if (i <= x+d1+d2+1) cnt++;
        for (int j = y+d2-cnt; j <= N; j++){
            tmp_arr[i][j] = 4;
        }
    }
    for (int i = 1; i<=N; i++){
        for (int j = 1; j <=N; j++){
            num[tmp_arr[i][j]]+= map[i][j];
        }
    }
    for (int i = 1; i <=5; i++){
        min_num = min(min_num,num[i]);
        max_num = max(max_num,num[i]);
    }
    return max_num - min_num;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i<=N; i++){
        for (int j=1 ; j<=N; j++){
            cin >> map[i][j];
        }
    }
    for (int x = 1; x < N; x++){
        for (int y = 2; y < N; y++){
            for (int d1 = 1; d1 <= y; d1++){
                for (int d2 = 1; d2 <= N-y; d2++){
                    if (x+d1+d2>N || y-d1 <=0 || y+d2 >N) continue;
                    int diff = go(x,y,d1,d2);
                    ans = min(ans,diff);
                }
            }

        }
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
  • 먼저, 처음에 제출했더니 시간초과가 났습니다.
  • 시간초과가 날 일이 없고, 배열크기도 잘 설정해놨는데 이유를 알 수 없었습니다.
  • 선거구를 정할 때, 선거구 숫자를 넣는 배열을 지역변수로 일정범위만 5로 초기화시켜주면서 진행한것이 원인이었던 것 같습니다.
  • 이를 전역변수로 변경하였습니다.
  • 또 다른 실수로는, (x,y),(d1,d2)를 정하고 범위를 벗어나는 경우 시뮬레이션을 진행하지 않도록 해야하는데, 그 범위를 잘못설정하였습니다.
  • 기존에 d1+d2>N인 경우 진행하지 않도록 잘못 설정하였습니다.
  • x+d1+d2>N, y-d1<=0, y+d2>N 범위를 하나라도 벗어나면 진행하지 않도록 변경하였습니다.
제출결과
  • 12 ms

마무리

  • 범위 설정이 아주 까다로운 문제였습니다.
  • 삼성역량테스트기출문제로 범위체크가 까다로운 문제나 배열 회전시키는 문제를 아주 자주 내는 것 같습니다.
  • 유의해서 다시한번 풀이해봐야겠습니다.
 BOJ

Related Posts