[1780번] 종이의 개수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 분할 정복

분할 정복 문제이다.

[1992번] 쿼드트리 :: http://www.crocus.co.kr/808 문제와 똑같은 문제이기도 하다.

쿼드트리 문제는 짝수이기에 더많은 분할이 필요없지만, 종이의 개수 문제는 3^k승이기에 분할을 9등분으로 해야한다.

그것 말고는 분할 정복 문제 중 이런 문제는 코드가 별반 차이가 없다.

시간을 좀 더 단축하기 위해서는, cout을 printf로

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

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

            if (map[i][j] != first)

            {

                chk = false;

                break;

            }

에서

if(n != 1)   

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

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

            if (map[i][j] != first)

            {

                chk = false;

                break;

            }

으로 바꾸면 시간을 좀 더 단축할 수 있다.

[궁금한 점] :: 그런데 void형이 아닌 int형으로는 왜 문제가 해결이 되지 않는지 모르겠다.

https://www.acmicpc.net/board/view/14881 여기 질문을 올려뒀는데 누군가가 이 글을 본다면 필자의 질문에도 답을 해주었으면 한다..

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <iostream> #include <cstdio>   using namespace std;   int map[2300][2300]; int cnt[4];   int total;   void solve(int n, int y, int x, int jump) {     int first = map[y][x];       bool chk = true;       for(int i = y; i < y + n; i ++)         for(int j = x; j < x + n; j++)             if (map[i][j] != first)             {                 chk = false;                 break;             }       if (chk)         cnt[first + 1]++;       else     {         solve(n / 3, y + jump * 0, x + jump * 0, jump / 3);         solve(n / 3, y + jump * 0, x + jump * 1, jump / 3);         solve(n / 3, y + jump * 0, x + jump * 2, jump / 3);           solve(n / 3, y + jump * 1, x + jump * 0, jump / 3);         solve(n / 3, y + jump * 1, x + jump * 1, jump / 3);         solve(n / 3, y + jump * 1, x + jump * 2, jump / 3);           solve(n / 3, y + jump * 2, x + jump * 0, jump / 3);         solve(n / 3, y + jump * 2, x + jump * 1, jump / 3);         solve(n / 3, y + jump * 2, x + jump * 2, jump / 3);     } }   int main() {     int n;     scanf("%d", &n);         total = n;       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             scanf("%d", &map[i][j]);       solve(n, 0, 0, n / 3);       cout << cnt[0] << endl;     cout << cnt[1] << endl;     cout << cnt[2] << endl;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus