문제

in Blog_old on Boj, 삼성sw역량테스트기출, C++

링크

$N\times N$정사각형 격자판 각 칸에 인구수가 주어진다. 규칙에 따라 격자판을 다섯 구역으로 나눌 수 있는데, 가장 인구수가 많은 구역과 적은 구역의 차이의 최소값을 구하는 문제이다.

접근

경계선은 45도 기울어진 직사각형 모양으로 만들어지고, 이에 따라 1번에서 5번까지 구역이 나누어진다. 기준점의 위치와 직사각형 크기는 $x,y,d_1,d_2$값에 따라서 결정되므로, 일단 4중 for문을 사용한다.

for문 안에서는 유효한 값인지 확인하고, 각 구역의 인구수 합을 계산하여 구하려는 최종 값을 업데이트 해준다. 여기서 두 가지 정도 고민할 점이 있는데,

  1. 어떤 $x,y,d_1,d_2$값이 유효한 값인가? 즉 for 문을 어떤 범위에서 돌려야 하는가?
  2. 어떤 칸이 어떤 구역에 해당하는지 어떻게 확인할 것인가?

하는 것이다. 1번의 경우 그냥 모두 0부터 N-1까지(zero based index일 경우)로 for문을 짠 다음, 네 개의 기준점 좌표가 모두 격자판 안의 유효한 좌표인지 확인하면 간단하다. 대신 이러면 자명하게 불가능한 값에 대해서도 루프가 실행되므로, 나는 규칙에 맞는 값들만 범위에 해당하도록 조금 바꿨다.

즉, 직사각형의 네 꼭지점이 격자판 안에 있도록 하려면 그냥 for문 안에서 if (x+d1+d2>=N || y-d1<0 || y+d2>=N) continue로 하면 되는데, 이렇게하면 불필요한 루프가 더 실행될 것 같아서 $d_1$을 0부터 $y$까지, $d_2$를 $N-y-1$까지 범위로 잡고 $x + d_1 + d_2 < N$인지만 확인했다.

2번의 경우 걱정한것 보다는 쉽다. 먼저 경계선 안쪽에 있는 구역을 5번으로 분류해버리고, 나머지 구역에 대해서는 문제 설명에 나온 규칙대로 else if 해주면 된다.

5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.

  • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
  • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
  • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
  • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

주의할 점

문제를 읽고 난 뒤, 사각형의 꼭짓점 중 하나가 격자판 밖으로 나가도 되는것인지(그래서 직사각형 모양이 아니라 오각형 모양으로 5번 구역이 생겨도 되는지) 모호했는데, 일단 아닌 것 같다. 모든 꼭짓점이 격자판 구역 안으로 들어와야 한다.

또, 구역을 분류할때, 0부터 시작하는 index인지 1부터 시작하는 index인지 잘 생각하며 처리해주자.

Code

링크

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>

using namespace std;

int N, M;
int A[20][20];
int MAX_INT = 100003;

int solve(int x, int y, int d1, int d2) {
    int sum[5] = {0};
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (x + y <= i + j && i + j <= x + y + 2 * d2 && x - y <= i - j && i - j <= x - y + 2 * d1) {
                sum[4] += A[i][j];
            } else if (i < x + d1 && 0 <= j && j <= y) {
                sum[0] += A[i][j];
            } else if (i <= x + d2 && y < j && j <= N - 1) {
                sum[1] += A[i][j];
            } else if (x + d1 <= i && i <= N - 1 && j < y - d1 + d2) {
                sum[2] += A[i][j];
                // } else if (x + d2 < i && i <= N - 1 && y - d1 + d2 <= j && j <= N - 1) {
            } else
                sum[3] += A[i][j];
        }
    }
    sort(sum, sum + 5);
    return sum[4] - sum[0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // get input
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }
    int ans = MAX_INT;

    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            for (int d1 = 0; d1 <= y; d1++) {
                for (int d2 = 0; d2 < N - y; d2++) {
                    // if (x+d1+d2>=N || y-d1<0 || y+d2>=N) continue
                    if (x + d1 + d2 < N) {
                        ans = min(ans, solve(x, y, d1, d2));
                    }
                }
            }
        }
    }

    cout << ans;
    return 0;
}