BOJ 2225 - 합분해

링크: https://www.acmicpc.net/problem/2225

문제의 예시로 n=20, k=2일 때 나올 수 있는 경우의 수는

 0 + 20

 1 + 19

 2 + 18

   ...

19 + 1

20 + 0

로 총 21개이다.

풀이

n=20이고 k=3이라면, 경우의 수는 아래와 같은 모양으로 전개된다.

(n=20, k=3) =

   (n=20, k=2)

+ (n=19, k=2)

+ ...

+ (n=1, k=2)

+ (n=0, k=2)

3개의 수를 n=20 내에서 고르는 경우의 수 = 

   첫 번째 수로 0을 사용하고, 나머지 2개의 수를 n=20 내에서 고르는 경우의 수

+ 첫 번째 수로 1을 사용하고, 나머지 2개의 수를 n=19 내에서 고르는 경우의 수

+ ....

작은 문제로 쪼개어 해결이 가능하다. dp 테이블을 두고 메모이제이션했다.

k=1이면 가능한 경우는 n을 선택하는 1가지 밖에 없으므로 f(n, 1) = 1 이다.

코드