오일러 프로젝트 76

76번 문제는 예전 31번(영국화폐 조합의 수)와 사실상 같은 문제이다. 임의의 자연수 N 을 N보다 작은 자연수들의 합으로 나타내는 경우의 수를 분할수라고 하는데, 이는 결국 1…N-1 의 액면가를 가지는 동전들로 N 만큼의 금액을 만드는 것과 동일한 연산이다.

문제

숫자 5를 자연수의 합으로 나타내는 데는 모두 여섯 가지 방법이 있습니다.


4+ 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

그러면 숫자 100을 두 개 이상의 자연수의 합으로 나타내는 방법은 모두 몇 가지나 됩니까?

풀이

1~99원짜리 동전이 있을 때, 100원을 만드는 방법의 수와 동일하다.

def getWays(n):
  ways = [1] + [0] * n
  for i in range(1, n):
    for j in range(i, n+1):
      ways[j] += ways[j-i]
  return ways[n]
print(getWays(100))