백준 1780 - 종이의 개수

문제

 

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

 

풀이

 

N * N 배열 안에 모든 수를 검사한다. 검사 시작점은 왼쪽 위를 기준으로 한다. 만약 모든 수가 같지 않으면 배열을 9개로 나누고 각 배열에서도 왼쪽 위를 검사 시작점으로 검사를 진행하면 된다. 

주어진 N은 3의 제곱 배수다. 그리고 배열의 모든 수가 같지 않으면 똑같은 크기로 9개를 나눠야 하므로 N을 3으로 나눈 수로 배열을 나눠주면 된다. 

이중 for문을 이용해서 9개로 나눈 배열에 대해서 재귀함수를 호출해서 문제를 해결할 수 있다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
const int MAX = 3*3*3*3*3*3*3;
 
int N;
int arr[MAX][MAX];
int result[3];
 
bool check(int x, int y, int n)
{
    int v = arr[x][y];
 
    for (int i=x; i<x+n; i++)
    {
        for (int j=y; j<y+n; j++)
        {
            if (arr[i][j] != v)
                return false;
        }
    }
 
    return true;
}
 
void f(int x, int y, int n) 
{
   if (check(x, y, n))
   {
       result[arr[x][y]+1]++;
       return;
   }
 
   int m = n/3;
   for (int i=0; i<3; i++)
        for (int j=0; j<3; j++)
            f(x + i*m, y + j*m, m);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N;
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            cin >> arr[i][j];
 
    f(0, 0, N);
 
    for (int i=0; i<3; i++)
        cout << result[i] << '\n';
 
    return 0;
}