문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

합 N을 만드는 정수 K개 중에서, 하나의 값은 미리 정해두고 나머지 (k-1)개의 조합을 구하는 방식으로 모든 경우의 수를 구할 수 있다. 이처럼, 문제를 쪼개서 풀 수가 있고, sub-problems이 반복되기 때문에 Dynamic Programming으로 풀 수 있다.

Algorithm

위의 생각을 바탕으로, 다음과 같은 Top-Down recursive 방식을 생각할 수 있다.

solve( N, K ):

		 					(n,k)
               /       /  		    	\ 			\
        (0, k-1), (1, k-1)    ...   (n-1, k-1), (n, k-1)
         / 			/         ...       |			\
         					  ...				  (0, k-2), ... (n, k-2)
                              ...
                              ...
                              ...

위의 (n,k)에서 시작하는 방식을 기반으로, (0, 1)부터 (n,k)까지 작성해나가는 Bottom-Up 방식으로 개선할 수 있다.

dp[n][k]에 대하여
dp[i][j] = dp[i][j-1]+ dp[i-1][j]

따라서, 시간 복잡도는 O(nk)이다.

Data Structure

Table을 작성하기 위한, (n+1) x (k+1)의 2D Array가 필요하다.

결과

Other

이처럼, DP를 쓰기 위해선, 문제를 쪼갤 수 있어야하고, 같은 문제가 반복적으로 나타야한다.
이 조건을 갖추면, 직관적으로 떠올릴 수 있는 Top-Down 방식을 생각하고, 순서를 뒤집어서 Bottom-Up 방식으로 개선하면 된다.