[백준 1780] 종이의 개수 [C]

백준 - 1780

---

풀이

9등분을 하고, n/3만큼 좌표를 (x, y) 증가시켜 Divide and Conquer 하면 된다.

N만큼의 종이가 모두 같을 때, 탐색을 중단해야 하므로 중단 조건을 함수로 만들어 풀이했다.

---

소스코드

#include <stdio.h>
int paper[2187][2187], I[3];
int all_same_paper(int x, int y, int n){
    int temp = paper[x][y];
    for (int i = x; i < x+n; i++)
        for (int j = y; j < y+n; j++)
            if (paper[i][j] != temp)
                return 0;
    return 1;
}
void division(int x, int y, int n){
    if (all_same_paper(x, y, n))
        I[paper[x][y] + 1]++;
    else 
        for (int i = x; i < x+n; i += n/3)
            for (int j = y; j < y+n; j += n/3)
                division(i, j, n/3);
}
int main(){
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N*N; i++)
        scanf("%d", &paper[i/N][i%N]);
    division(0, 0, N);
    printf("%d\n%d\n%d", I[0], I[1], I[2]);
}

---

출처

1780번: 종이의 개수