DeveloperOC

🔗 색종이 만들기

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

📌 문제 요약

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다

입력: 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
출력: 첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

💡 접근 방법

N*N 크기의 색종이에서 확인해야할 부분 색종이는
시작 지점 : [0, 0] 크기 : N/2
시작 지점 : [0, N/2] 크기 : N/2
시작 지점 : [N/2, 0] 크기 : N/2
시작 지점 : [N/2, N/2] 크기 : N/2
총 네개이다.

네개의 색종이 모두 같은 값일 때 하나의 색종이로 취급하기 때문에
크기가 1이 될 때까지 재귀시키고 각 종이의 값을 비교해 카운팅 해주면 된다.

⚠️ 처음에 했던 실수

💻 코드

#include <iostream>

using namespace std;

int N;
int paper[129][129];

int white;
int blue;

int paperCheck(int r, int c, int cnt)
{
    int half = cnt / 2;

    int a,b,c2,d;
    
    if(half == 1)
    {
        a = paper[r][c];
        b = paper[r][c + half];
        c2 = paper[r + half][c];
        d = paper[r + half][c + half];
    }
    else
    {
        a = paperCheck(r, c, half);
        b = paperCheck(r, c + half, half);
        c2 = paperCheck(r + half, c, half);
        d = paperCheck(r + half, c + half, half);
    }
    

    if(a == b && a == c2 && a == d)
        return a;

    if(a == 1)
        blue++;
    if(b == 1)
        blue++;
    if(c2 == 1)
        blue++;
    if(d == 1)
        blue++;
        
    if(a == 0)
        white++;
    if(b == 0)
        white++;
    if(c2 == 0)
        white++;
    if(d == 0)
        white++;
        
    return 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N;

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            cin >> paper[i][j];

    int p = paperCheck(0,0, N);

    if(p == 1)
        blue++;
    if(p == 0)
        white++;

    cout << white << '\n' << blue;
    return 0;
}