BOJ2630 색종이 만들기

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

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

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

해설

구현해야 할 목록은 다음과 같다.

구간의 색이 같은지 확인
다르다면 구간을 나눠서 1번으로, 같다면 카운팅

이런 구간의 색이 같은지 확인을 하는 방법을 먼저 생각해보자.
1 1 0 0
1 1 0 0
1 0 0 0
0 1 0 0

구간의 범위를 구한 후 for문을 돌려서 구하면 될꺼같다.
합이 0 또는 1이면 카운팅

다르다면 길이를 2로 나눈 후 1번 작업을 하나의 정사각형 칸이 될때까지 반복한다.

접근방식 1 (recursive)

#include <bits/stdc++.h>
using namespace std;
int n,cntW=0,cntB=0;
int a[129][129];
void f(int x,int y,int z){
    if(z==0)return;
    int s=0;
    for(int i=x; i<x+z; i++){
        for(int j=y; j<y+z; j++){
            s+=a[i][j];
        }
    }if(s==z*z){
        cntB++;
    }else if(s==0){
        cntW++;
    }else{
        z/=2;
        f(x+z,y+z,z);
        f(x+z,y,z);
        f(x,y+z,z);
        f(x,y,z);
    }
}
int main(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
        }
    }f(1,1,n);
    cout << cntW << '\n' << cntB;
}