✅ DP

문제

링크

1. 문제 접근 및 해결 로직

$dp[k][n]$ : k개를 더하여 n이되는 경우의 수 라고 하자.
$dp[1][n]$ 인 경우는 전부 1이다. 1개를 더해 n인 경우는 n 자기자신 하나만 더한 경우 뿐이다.

$dp[k-1][n...1]$ 와 $dp[k][n]$ 의 관계를 생각해보자.

1. $dp[k-1][n]$ 에서 (k-1)개를 사용하여 이미 (n)이 되었으므로 0을 더해 (k)개 사용하여 (n)을 만들면 된다.
2. $dp[k-1][n-1]$ 에서 (k-1)개를 사용하여 (n-1)을 만들었으므로 1을 더해 (k)개를 사용하여 (n)을 만들면 된다.
3. $dp[k-1][n-2]$ 에서 (k-1)개를 사용하여 (n-2)을 만들었으므로 2을 더해 (k)개를 사용하여 (n)을 만들면 된다.
   ...
   순서대로 0,1,2,...을 더했지만 dp는 경우의 수 이므로 행위 자체를 하나로 세면된다.
   이과정을 반복하면 결국 아래와 같은 점화식이 도출된다.
   $dp[k][n]=dp[k-1][n]+dp[k-1][n-1]+dp[k-1][n-2]+...$

• 정의
  $dp[k][n]$ : k개를 더하여 n이되는 경우의 수
• 구하는 답
  $dp[k][n]$
• 초기값
  $dp[1][n]=1$
• 점화식
  $dp[k][n]=dp[k-1][n]+dp[k-1][n-1]+dp[k-1][n-2]+...$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항