Sum Decomposition

문제 복기

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 : 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력 : 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

Ex1) I : 20 2 O : 21

알고리즘 생각

1,2,3 더하기 문제 응용 & 확장판

변수가 N,K가 있기 때문에 1차원보다는 2차원 DP라고 생각해야한다!

1. D[k][n] : k개 정수로 합이 n을 만드는 경우의 수

2. D[k][n] = ΣD[k-1][n-L] (0<=n<=N, 0<=L<=n) L은 마지막에 오는 수를 의미한다. 이때 (new)K = K-1, (new)N = N-L 이 되고 나면 L은 N-L 이하의 수를 갖는다. (new)N = N-L에서 L은 문제에서 주어지는 조건으로 인해 0<=L<=N 이므로, N = N ~0 즉, 0<=newN<=N 이 된다. 이때 N-L은 변수 N과 같기 때문에 L의 범위는 0이상 n이하라고 한다.

• 코드 구현 시 유의할 점 위의 점화식을 계산할 때 필요한 d[0][0] = 1로 먼저 셋팅해준다!