BOJ 2294 - 동전 2

문제

---

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

---

만약 n가지 종류의 동전이 서로 배수 관계라면 그리디 알고리즘으로 해결이 가능했다.

하지만 배수 관계가 아닌 경우 다이나믹 프로그래밍으로 해결해야한다.

위 문제의 경우 동전이 배수 관계인 경우, 아닌 경우 모두 다루기 때문에 다이나믹 프로그래밍으로 접근한다.

 

1. 처음 접근은 메모이제이션하려는 DP의 정의를 내린다.

    $dp[k]$ : $k$원을 만드는데 동전의 최소 사용 횟수

 

2. 점화식을 세운다

   $dp[k] = min(dp[k-coin[i] + 1)$

  점화식의 의미는 k원에서 현재 가지고 있는 가능한 모든 동전을 빼준 최솟값(min)이다.

    

bottom-up

 

top-down