✅ DP

문제

링크

1. 문제 접근 및 해결 로직

1. k-1원에서 k원을 만드는 방법은 k-1원에 1원을 더하는 것이다.
2. k-2원에서 k원을 만드는 방법은 k-2원에 2원을 더하는 것이다.
   ...
3. k-j원에서 k원을 만드는 방법은 k-j원에 j원을 더하는 것이다.

• 따라서 k원을 만드는 모든 경우의 수는 k-1, k-2, k-3, ..., 1원을 만드는 경우의 수를 모두 더한 것과 같다.

• 주의해야 할 점은 k-1원을 만드는 모든 경우의 수도 k-2, k-3, ..., 1원을 만드는 경우의 수를 모두 더한 것과 같으므로
  만들 수 있는 경우의 수를 중첩해가면서 더해야 한다. (아래 점화식 참고)

• 그리고 사용할 수 있는 동전은 입력으로 정해지므로 3,4,5 원이 주어졌다면
  k-3,k-4,k-5를 만들 수 있는 경우의 수를 중첩해가면서 더하면 된다.

• 정의
  $f(i)$ : $i$원을 만들 수 있는 모든 경우의 수
• 구하는 답
  $f(k)$
• 초기값
  $f(0)=1$ : 0원을 만들 수 있는 모든 경우의 수는 아무 동전을 선택하지 않은 경우 이므로 0가지가 아니라 1가지이다.
• 점화식
  $f(i)+=f(i-coin[j]),(min(coin)<=i<=k,0<=j<n)$

2. 코드

3. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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