이 정사각형은 2×2 크기의 정사각형들로 나뉘어 압축됩니다. 작은 정사각형들이 압축된 상태는 다음 그림과 같습니다.

▲ 그림 5-3 2×2 크기의 정사각형들이 압축된 과정

2×2 정사각형이 압축되는 과정은 4×4 정사각형이 압축되는 과정과 같은 로직을 사용하므로 다시 1×1 정사각형으로 나뉘는 과정을 진행하지 않고 직접 0과 1의 개수를 세어 주면 됩니다.

이렇게 작은 부분 문제인 2×2 정사각형들의 압축 결과를 구했습니다. 4×4 정사각형을 압축했을 때 0과 1의 개수는 2×2 정사각형들의 압축 결과를 모두 합친 결과입니다. 모든 결과를 합쳐 보면 0이 5개, 1이 5개가 되므로 4×4 정사각형은 다음 그림과 같이 압축됩니다.

▲ 그림 5-4 압축된 4×4 정사각형