[BOJ 1780] 종이의 개수

문제 출저 : https://www.acmicpc.net/problem/1780

 

풀이 :

 

분할 정복 문제입니다.

만약 전체가 같은 수로 이루어 지지 않았다면 전체를 9구역으로 분할 한 후 계속 검사해 나갑니다.

저는 type 변수를 스위치 처럼 사용 하였습니다.

현재 분할 된 부분의 전체를 탐색하고

스위치가 켜지면 하나의 수로 채워진 종이가 아닌 경우이고 꺼져있으면 하나의 수로 채워진 종이라고 인식합니다.

#include<stdio.h>
 
int n,arr[2187][2187],score[3];
 
void divide(int x,int y,int size)
{
    if (size==1)
    {
        arr[y][x] == 1 ? score[2]++ : arr[y][x] == 0 ? score[1]++ : score[0]++;
        return;
    }
    int check = arr[y][x],type=0;
    for (int i = y; i < y + size&&!type; i++)for (int j = x; j < x + size&&!type; j++)if (arr[i][j] != check)type = 1;
    if (!type)
    {
        arr[y][x] == 1 ? score[2]++ : arr[y][x] == 0 ? score[1]++ : score[0]++;
        return;
    }
    else
    {
        size /= 3;
        for (int i = 0,j=x; i < 3; i++,j+=size)divide(j, y, size);
        for (int i = 0,j=x; i < 3; i++,j+=size)divide(j, y+size, size);
        for (int i = 0,j=x; i < 3; i++,j+=size)divide(j, y+size*2, size);
    }
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf("%d", &arr[i][j]);
    divide(0, 0, n);
    for (int i = 0; i < 3; i++)printf("%d\n", score[i]);
}