백준 1780번 종이의 개수

문제 링크입니다: https://www.acmicpc.net/problem/1780

백준 1992번 쿼드트리(http://jaimemin.tistory.com/1072)와 비슷한 문제였습니다.

4분할을 하는 대신 9분할을 하면 되는 문제였습니다.

#include <iostream>

using namespace std;

 

const int MAX = 2187; //3^7

 

int N;

int arr[MAX][MAX];

int result[3];

 

void func(int n, int y, int x)

{

        //기저 사례

        if (n == 1)

        {

                 result[arr[y][x] + 1]++;

                 return;

        }

 

        bool minus = true, zero = true, plus = true;

        for(int i=y; i<y+n; i++)

                 for(int j=x; j<x+n; j++)

                         if (arr[i][j] == -1)

                         {

                                 zero = false;

                                 plus = false;

                         }

                         else if (arr[i][j] == 0)

                         {

                                 minus = false;

                                 plus = false;

                         }

                         else

                         {

                                 minus = false;

                                 zero = false;

                         }

 

        if (minus)

                 result[0]++;

        else if (zero)

                 result[1]++;

        else if (plus)

                 result[2]++;

        else

        {

                 int div = n / 3;

                 func(div, y, x);

                 func(div, y, x + div);

                 func(div, y, x + 2 * div);

 

                 func(div, y + div, x);

                 func(div, y + div, x + div);

                 func(div, y + div, x + 2 * div);

 

                 func(div, y + 2 * div, x);

                 func(div, y + 2 * div, x + div);

                 func(div, y + 2 * div, x + 2 * div);

        }

        return;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> arr[i][j];

 

        func(N, 0, 0);

        for (int i = 0; i < 3; i++)

                 cout << result[i] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~