boj 1780

boj 1780 종이의 개수 c++

 

 

나는 왜 이 유형이 잘 안풀릴까.

아이디어는 이렇다.

가로 n, 세로 n개의 board가 모두 같은 수로 채워진 경우 그 수를 ++.

그렇지 않은 경우 board를 다시 9개로 나누고 위를 반복.

매우 간단하지만 머릿 속에서 이리저리 굴리다 보면 약간은 지끈지끈 하다.

 

그리고 재귀에는 어디서부터 재귀를 시작할지가 중요하다. 이를 위해 재귀 함수에 시작점에 대한 정보도 함께 넘겨준다.

(start_i, start_x)

 

정답코드:

#include <bits/stdc++.h>
using namespace std;

int N;
int answer[3];
// 3^7 = 2187
char board[2200][2200];

void solve(int start_i, int start_j, int n)
{
    bool is_all_same = true;
    char first_element = board[start_i][start_j];

    for (int i = start_i; i < start_i + n; i++)
    {
        for (int j = start_j; j < start_j + n; j++)
        {
            if (board[i][j] != first_element)
            {
                is_all_same = false;
                break;
            }
        }
        if (is_all_same == false)
        {
            break;
        }
    }

    if (is_all_same == true)
        answer[first_element] += 1;
    else
    {
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                solve(start_i + i * (n / 3), start_j + j * (n / 3), n / 3);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int t;
            cin >> t;
            t += 1;
            board[i][j] = t;
        }
    }
    solve(0, 0, N);
    cout << answer[0] << endl;
    cout << answer[1] << endl;
    cout << answer[2] << endl;
}

 

백준 1780 종이의 개수 c++