[EP 078] 동전 나누기

문제 78 : p(n)을 n개의 동전을 무더기로 나누는 경우의
수라고 하자. 예를 들어서, 5개의 동전이 있다면, 다음과 
같이 7가지 방법이 있어서, p(5) = 7이 된다.

ooooo
oooo o
ooo oo
ooo o o
oo oo o
oo o o o
o o o o o

해법 :
Q(n, m) 을 n개의 동전을 나눌 때 가장 큰 무더기를 이루는 
갯수가 m개인 경우의 수라고 한다. 위 예에서 보면,
 Q(5,5) = 1
 Q(5,4) = 1
 Q(5,3) = 2
 Q(5,2) = 2
 Q(5,1) = 1
이 되는 것을 알 수 있다.

이렇게 정의한 Q(n, m)에서 다음과 같은 식이 항상 성립함을 
알 수 있다.
 Q(n, n) = 1
 Q(n, 1) = 1
              m
 Q(n, m) =   sum  Q(n-m, i) 
            i = 1

마지막 식은 n개의 동전에서 m개의 무더기를 먼저 떼어놓은 후 
남은 [ n-m ] 개의 무더기를 나누는 경우의 수를 생각해 보면 
금방 알 수 있다.