어떤 문제인가?

분할 정복을 이용해 부분문제를 만들고 해결하는 문제.

시행착오 횟수

한 번에 해결함.

1차 시도 : AC

색종이를 가로, 세로로 절반으로 자른다.

4x4 색종이를 예로 들자.
처음에는 (0,0)에서 시작해 (3,3)까지 색이 같은지 확인한다.
-> 다르다면 다음과 같이 쪼개어 해당 범위 내에서 색이 같은지 확인한다.

1. (0,0)에서 (1,1)까지.
2. (2,0)에서 (3,1)까지.
3. (0,2)에서 (1,3)까지.
4. (2,2)에서 (3,3)까지.

-> 만일 색상이 모두 같다면, 하얀색 색종이 혹은 파란색 색종이 갯수를 하나씩 올리면 된다.

위의 절차를 반복하여 크기가 1이 된다면 색상만 확인한다.

함수 꼴로 치환하면 다음과 같다. $x,y$는 초기 좌표, $L$은 길이이며, $2^k$ 꼴이다.

위를 코드로 옮기면 다음과 같다.

#include <stdio.h>

char D[129][129];
unsigned W=0,B=0;

void R(int x, int y, int L) {
	int i,j,c=D[x][y];
	for(i=x;i<x+L;i++) {
		for(j=y;j<y+L;j++) {
			if(c!=D[i][j]) {
				if(L>1) {
					R(x,y,L/2);
					R(x,y+L/2,L/2);
					R(x+L/2,y,L/2);
					R(x+L/2,y+L/2,L/2);
					return;
				}
			}
		}
	}
	if(c) B++;
	else W++;
}

int main()
{
	int N,i,j;
	scanf("%d",&N);
	for(i=0;i<N;i++) {
		for(j=0;j<N;j++) scanf("%u",D[i]+j);
	}
	R(0,0,N);
	printf("%d\n%d",W,B);
}

다른 분들의 풀이

전체적인 흐름은 매우 비슷하므로 생략한다.

한줄평

무난한 문제였다. 분할 정복 입문용으로 딱이다.