궤도

문제 풀이 이 문제를 풀기 위해선 2차원 dp배열을 사용해야 한다. dp[i][j]를 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수라고 하자. 쉽게하기 위해 N=4, K=3이라고 하자. 0 1 2 3 4 1 1 1 1 1 1 2 1 3 1 먼저 K=1인 경우 dp[1][j]=1일 것이다. 0부터 j까지의 정수 1개를 더해서 그 합이 j가 되는 경우의 수는 j 스스로를 사용하는 경우 1개 뿐이기 때문이다. 다음으로 N=0인 경우 dp[i][0]=1일 것이다. 몇개의 숫자를 사용한들 그 합이 0이 되기 위해선 0만을 i개 더하는 경우 1개 뿐이기 때문이다. 그렇다면 K=2, N=1인 경우를 보자. 0부터 1까지의 정수 2개를 더해서 그 합이 1이 되어야 한다. 그 합을 a+b+c+d+e...