예제 문제를 하나 풀면서 점진적인 개선을 어떻게 적용할 수 있나 살펴봅시다. $N(N \le 30)$개의 사탕을 세 명의 어린이에게 가능한 공평하게 나눠 주려고 합니다. 공평함의 기준은 받는 사탕의 총 무게가 가장 무거운 어린이와 가장 가벼운 어린이 간의 차이로 합시다. 사탕의 무게는 모두 20 이하의 정수입니다. 가능한 최소 차이는 얼마일까요?
이 문제를 푸는 가장 단순한 방법은 사탕을 나눠 주는 모든 방법을 하나씩 만들어 보는 것입니다. 각 사탕마다 셋 중 어느 어린이에게 줄 지를 결정한다고 하면 $3^N$, 즉 최대 205조 개의 방법을 만들어 보게 됩니다. 이는 죽기 전에 다 세어볼 수 있을까 엄두가 나지 않는 큰 수이지만, 사실 이 때 우리는 엄청나게 많은 수를 중복으로 세고 있습니다. 실제로 받은 사탕들이 서로 다르더라도 그 무게가 같다면 이 문제의 답은 같다는 점을 무시했기 때문입니다.
이 아이디어를 이용해 모든 방법을 만들어 보는 완전 탐색(6장) 대신 각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 너비 우선 탐색(29장)으로 문제를 풀 수 있습니다. 이 때 각 상태는 세 어린이가 가진 사탕의 양을 표현하는 세 개의 정수입니다. 우리는 어떤 어린이에게도 사탕이 없음을 나타내는 (0, 0, 0)에서 시작해, 사탕을 하나 줄 때마다 그 어린이가 가진 사탕의 양을 늘립니다. 이렇게 하면 실제로 가진 사탕들이 다르더라도 그 무게가 같은 경우 하나의 상태로 취급해, 중복을 제거할 수 있습니다. 이 상태 공간의 크기는 얼마일까요? 사탕의 최대 무게는 20이므로, 각 어린이가 가진 사탕의 양은 $0$에서 $20\times N$ 사이입니다. 따라서 각 상태에 대해 방문 여부를 저장하려면 크기가 $(20\times N+1)^3 \le 601^3$(대략 2억)인 배열을 잡아야 합니다.
2억은 대개 시간 제한 안에 탐색할 수 있는 크기입니다만, 이 문제의 답이 최대 얼마인지 생각해 보면 이 방법을 더 최적화할 수 있습니다. 사탕을 가장 많이 받은 어린이와 가장 적게 받은 어린이의 차이가 20 이상이었다고 가정해 봅시다. 사탕의 최대 무게는 20이므로, 이때 사탕을 가장 많이 받은 어린이가 가장 적게 받은 어린이에게 사탕을 하나 준다고 해도 사탕의 총량이 역전되지 않습니다. 그러면 이 둘이 가진 사탕의 양의 차이는 항상 감소합니다. 이렇게 하면 항상 원래보다 더 공평한 답을 얻을 수 있기 때문에, 차이가 20 이상인 경우는 절대로 최적의 답이 될 수 없다는 것을 알 수 있지요. 따라서 넉넉잡아도 사탕을 가장 많이 받은 어린이가 $\frac{20\times N}{3} + 20$ 넘게 사탕을 받는 경우는 무시해도 됩니다. 그러면 실제로 할당해야 하는 배열의 크기는 $(\frac{20\times N}{3} + 20)^3 \le 220^3$(대략 1000만)으로 줄어듭니다.
이 정도면 충분히 문제를 풀 수 있을 것 같지만, 문제를 푸는 더 빠른 방법이 있습니다. 세 어린이 중 누가 가장 사탕을 적게 받고, 누가 가장 많이 받는지는 중요하지 않기 때문입니다. 세 어린이의 사탕의 총량이 (180, 190, 200)이건 (200, 190, 180)이건 우리의 답은 변하지 않지요. 따라서 세 어린이의 사탕의 총량이 항상 오름차순으로 정렬되어 있는 경우만을 탐색하도록 합시다. 서로 다른 세 수를 여섯 가지의 방법으로 나열할 수 있으므로, 이렇게 하면 경우의 수는 다시 대략 $\frac{1}{6}$으로 줄어듭니다. 결과적으로 대략 200만 개 이하의 경우의 수만을 탐색해 문제를 해결할 수 있지요. 이 과정에서 천재만이 떠올릴 수 있는 번뜩이는 영감은 필요없었지만, 처음에 생각했던 방법에 비해 검사해야 할 상태의 수가 1억분의 1로 줄어들었음을 알 수 있습니다.