- p(n,k) 함수는 숫자 n이 k 무더기로 나뉠 때의 경우의 수를 리턴한다.
- 문제에서 요구하는 것은 n을 분할할 수 있는 모든 경우의 수이므로 p(n,1) + p(n,2) + p(n,3) + ... + p(n,n-1) + p(n,n) 을 구해야 한다.
- p(n,k)는 무더기 원소가 1을 포함할 때와 아닐 때의 경우로 나눌 수 있다.
- 예를 들어 숫자 5를 2 무더기로 나눌 때 [4,1]은 1은 포함하고 [3,2]는 1을 포함하지 않는 경우다.
- p(n,k)가 원소 1을 포함하는 경우의 수는
p(n-1, k-1)로 나타낼 수 있다. 즉 1을 하나 따로 빼놓는 것이다.- 예를 들어 숫자 5을 3 무더기로 나눌 때 4를 2 무더기로 나누는 경우를 구한 다음 뒤에 1만 붙이면 반드시 1을 포함하는 경우가 된다.
- p(n,k)가 원소 1을 포함하지 않는 경우는
p(n-k, k)로 나타낼 수 있다. 일단 k개의 무더기에 1을 하나씩 갖다 놓는다. 그 다음에 나머지 n-k를 각 무더기에 분배한다. 그러면 모든 무더기는 반드시 2이상이다. - 그러므로
p(n,k) = p(n-1, k-1) + p(n-k, k) - 또 다른 방법은 k개의 무더기에 1씩 갖다 놓은 다음에 나머지 n-k를 자유롭게 분배하는 것이다. n-k를 1무더기에 몰아줄 수도, k 무더기로 골고루 나눌 수도 있다. 즉
p(n,k) = p(n-k,1) + p(n-k,2) + ... + p(n-k,k-1) + p(n-k,k)
- p(n,k)를 구할 수 있는 공식을 알아내서 동적 프로그래밍으로 풀기
- 인풋이 최대 30이어서 연산이 엄청 크지 않아 일반 재귀로 해도 성공하지만 메모이제이션을 쓰면 더 빠르다.
- 메모이제이션 쓸 때 list comprehension 으로 memo 리스트 초기화하지 말기 -> 빈 리스트 생성 후 for문으로 append
- 함수 밖에서 memo 리스트 초기화하고 param으로 넣어주기