공평하게 사탕을 나눠주기

문제

프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (구종만) 에 등장하는 사탕을 공평하게 나누어주는 문제를 공부하며 정리해 보았습니다.

문제

N(N<=30)개의 사탕을 세 명의 어린이에게 가능한 공평하게 나눠주려고 합니다. 공평함의 기준은 받는 사탕의 총 무게가 가장 무거운 어린이와 가장 가벼운 어린이의 차이로 합시다. 사탕의 무게는 모두 20 이하의 정수입니다. 가능한 최소 차이는 얼마일까요?

가장 단순한 형태의 답

책에서 설명한 대로 각 사탕마다 어떤 아이에게 줄 지를 계산한다면 경우의 수는 3 ** N (N은 최대 30) 이므로 최대 205조 개의 경우의 수가 나오게 됩니다.

Insight

• 실제로 받은 사탕이 서로 다르더라도 그 무게가 같다면 이 문제의 답은 같다는 점을 기억해야 합니다.

• 즉 사탕의 경우의 수를 세는 관점에서 -> 사탕의 무게의 경우의 수를 세도록 관점을 바꾸어야 합니다.

• 사탕의 무게의 경우의 수를 세어 봅시다: 사탕의 최대 무게는 20이고, 사탕을 한 개도 받지 않을 수도 있으니, 0 도 생각해야 합니다. 그리고 사탕의 개수는 최대 30개 입니다. 따라서 한 아이가 받을 수 있는 사탕 무게의 경우의 수는 30(사탕 개수) * 20(사탕 무게) 에 0인 경우의 수를 더해 총 601이 됩니다. 그리고 아이는 총 세 명이므로 601 ** 3 = (대략 2억), 모든 경우의 수는 2억개 입니다.

• 사탕의 경우의 수를 셀 때는 총 경우의 수 205조, 사탕 무게의 경우의 수를 셈으로서 경우의 수를 2 억개 까지 낮추었습니다.