이 상태가 나타내는 부분 문제는 해당 상태가 나타내는 정사각형 범위를 압축했을 때 남아 있는 0의 개수와 1의 개수를 구하는 것입니다. 즉, 상태는 다음과 같이 정의됩니다.

(offsetX, offsetY, size) = 좌표 (offsetX, offsetY)에서 시작하여 가로 길이와 세로 길이가 size인 정사각형을 압축했을 때 남아 있는 0과 1의 개수

종료 조건

상태가 나타내는 범위의 크기와 관계없이 범위 안 원소들이 모두 0이거나 1이면 정사각형은 더 이상 나누어지지 않고 하나의 숫자로 압축됩니다. 따라서 원소 구성에 따라 재귀가 종료되어야 합니다.

0의 개수가 zero, 1의 개수가 one일 때 결과 표기를 {0: zero, 1: one}이라고 한다면 종료 조건은 다음과 같이 정의할 수 있습니다.

점화식

점화식은 부분 문제를 해결하는 로직으로, 큰 문제를 작은 문제로 나타내야 합니다. 이 문제에서는 큰 정사각형이 4개의 작은 정사각형으로 나뉘어지고, 작은 정사각형을 압축한 결과를 모두 더한 것이 큰 정사각형의 결과가 됩니다. 예를 들어 다음 그림과 같이 4×4 크기의 정사각형이 구성되어 있습니다.

▲ 그림 5-2 4×4 크기의 정사각형