거스름돈 문제

그리디에서 해결되지 않는 문제가 있었다. 하지만 DP 알고리즘은 모든 동전 거스름돈 문제에 대해 항상 최적해를 찾을 수 있다.

1. 부분문제

• 문제의 입력요소: 동전의 종류, 거스름돈 n원
• 거스름돈을 1원씩 증가시키며 문제를 해결
• 1차원 배열 C로 표현

C[1] = 1원을 거슬러 받을 때 사용되는 최소의 동전 수
C[2] = 2원을 거슬러 받을 때 사용되는 최소의 동전 수
C[3] = 3원을 거슬러 받을 때 사용되는 최소의 동전 수
C[4] = 4원을 거슬러 받을 때 사용되는 최소의 동전 수
.
.
.
C[n] = n원을 거슬러 받을 때 사용되는 최소의 동전 수

• 점화식
  C[j] = min{C[j-d_i]+1}
  • j>= d_i
  • 1<=i<=k

2. 알고리즘

for i=1 to n
  C[i] = infinite
C[0] = 0
for j=1 to n
  for i=1 to k
    if (d_i <= j) && (C[j-d_i]+1 < C[j])
      C[j] = C[j-d_i] + 1

3. 시간 복잡도

for 문 2개: O(nk)