📖Problem

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

주어진 정사각형 종이를 하얀색(0)과 파란색(1)으로 칠해진 상태에서 동일한 색상의 부분 종이들을 분할하여 최종적으로 만들어진 하얀색 색종이와 파란색 색종이의 개수를 구하는 문제이다.

문제에서 대놓고 N/2로 나누며 더이상 자를 수 없을 때까지 반복한다고 말하며 ‘분할정복’을 쓸 수 있게 힌트를 제공하였다.

🔍Intuition

<aside> 📌 분할 정복 (divide and conquer)

</aside>

• 기법의 이름 그대로 큰 문제를 분할하여, 작은 문제들(Sub problems)로 나눈 뒤 그 결과들을 합쳐 기존의 큰 문제를 해결해나가는 기법
• 분할정복의 경우 재귀적으로 해결하는 방식이 가장 많이 사용되곤 한다.
• 대부분 재귀 함수를 통해 구현이 되며 메모리 제한이 없다면 비교적 빠르게 문제를 해결할 수 있다. 이는 재귀 함수를 통해 거의 절반으로 분리하기 때문에 가능하다.

분할 정복의 기본 형태의 Pseudo code

function F(x):
	if F(x)의 문제가 간단하다면:
			return F(x)를 직접 계산한 값
	else:
		x를 y1, y2로 분할
		F(y1), F(y2) 호출
		return F(y1), F(y2)로부터 F(x)를 구한 값

참고: https://dev-shin.tistory.com/entry/분할-정복Divide-and-Conquer, https://moz1e.tistory.com/85

🔍Approach

1. 종이의 크기 n과 정사각형의 칸의 색을 입력받아 colored_paper 리스트에 저장한다.
2. 하얀색 색종이의 개수는 white_cnt로, 파란색 색종이의 개수는 blue_cnt로 각각 0으로 초기화한다.
3. find_number_of_paper 함수는 색종이의 색을 분할정복하여 재귀적으로 파악하는 함수이다. x_start, y_start부터 시작하는 nxn 크기의 종이가 모두 같은 색인지 파악한다.
   1. 하얀색 종이의 경우, 모두 더하면 0이다. 따라서 범위 내에서 모두 더한 값이 0이라면 white_cnt의 값을 증가시킨다.
   2. 파란색 색종이의 경우, 1을 nn번 더한 값이다. 따라서 범위 내에서 모두 더한 값이 값이 nn이라면 blue_cnt의 값을 증가시킨다.
   3. 다른 색이 섞여있다면 종이를 4개로 분할하여 find_number_of_paper를 호출하여 동일한 작업을 시작한다.