[C/C++] 백준 #1780 종이의 개수(분할정복)

이번 문제는 무조건 분할을 한 후에, 그 결과를 토대로 결정을 하게 하는 문제입니다.

 

결국 분할 정복 문제입니다.  9개로 나누어 그 결과가 모두 같으면, 숫자의 종이를 합치는 것이죠.

 

원래의 문제는 하나의 종이에 모두 같은 숫자가 있다면 분할하지 않는 것이지만, 이렇게 하면, 상당히 많이 숫자를 세어야 합니다.

종이에 써져있는 숫자의 갯수가 최대 4백만개가 되므로, 숫자가 같은지 검사하는 것은 매우 비효율적입니다.

 

제가 사용한 방식은 무조건 분할한 다음, 9개가 모두 같은지 검사하여 같으면 종이를 합치는 것이죠.  시간 효율을 따져본다면, 다음과 같이 점화식을 낼 수 있습니다.

 

\[ T(1) = 1 \]

\[ T(n) = 9T(n/3) + 1 \]

 

형태가 되어서 \(O(n^2)\) 으로 볼 수가 있습니다.  결국 데이터의 개수와 같은 시간 복잡도를 가집니다.

 

paper cutting

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-------------------------------------------------------
//    baekjoon #1780
//        - by Aubrey Choi
//        - created at 2019-10-09
//-------------------------------------------------------
#include <stdio.h>

int c[3];

int count(char v[][2187], int y, int x, int n)
{
    if(n==1) { c[v[y][x]]++; return v[y][x]; }
    int s=-1, t;
    for(int i=0;i<3;i++) for(int j=0;j<3;j++)
    {
        t = count(v, y+i*(n/3), x+j*(n/3), n/3);
        if(s==-1) s=t; else if(s!=t) s=3;
    }
    if(s<3) c[s]-=8;
    return s;
}

int main()
{
    int n, s;
    char v[2187][2187];
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) { scanf("%d",&s); v[i][j]=s+1; }
    count(v, 0, 0, n);
    printf("%d\n%d\n%d\n", c[0], c[1], c[2]);
}