더북(TheBook)

이 알고리즘에서 가장 기본적인 단계는 단위 정사각형 하나를 덧붙이는 작업이다. 따라서 기본 단계 실행 횟수를 세는 것은 단위 정사각형 개수를 세는 것과 같다. 이 알고리즘을 n번 돌리고 나면 수평 방향으로 가장 긴 쪽에는 단위 정사각형이 총 (2n - 1)개 들어간다. 그 위아래로는 한 개에서 2n - 3개까지 홀수 개의 단위 정사각형들이 놓인다. 1에서 시작해 n - 1번째 홀수까지의 합은 (n - 1)2이므로 단위 정사각형 개수는 다음과 같이 구할 수 있다.

2(1 + 3 + ⋯ + (2n - 3)) + (2n - 1)

= 2(n - 1)2 + (2n - 1) = 2n2 - 2n + 1

또는 i번째(1≤in) 반복 단계에서 새로 덧불이는 단위 정사각형 개수가 4(i - 1)이라는 점을 활용할 수도 있다. 이 알고리즘을 n번 반복한 후 단위 정사각형의 총 개수는 다음과 같이 계산할 수 있다.

1 + 4·1 + 4·2 + ⋯ + 4(n - 1) = 1 + 4(1 + 2 + ⋯ + (n - 1))

= 1 + 4(n - 1)n/2 = 2n2 - 2n + 1

이렇게 표준적인 기법을 이용하는 것도 좋지만 이 문제에만 적용할 수 있는 특별한 성질은 없는지도 따져보면 좋다. 여기서는 n번째 반복 후에 만들어지는 도형의 대각선을 활용해 단위 정사각형 개수를 셀 수도 있다. 그림을 잘 보면 단위 정사각형 n개로 이루어지는 대각선 n개와 단위 정사각형 n - 1개로 이루어지는 대각선 n - 1개가 서로 번갈아 배치되어 있다. 따라서 단위 정사각형의 총 개수는 n2 + (n - 1)2 = 2n2 - 2n + 1개가 된다.

비슷한 문제로 삼각형 개수 퍼즐(2.052)을 들 수 있다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.