모든 동전들을 비교해보면서 최소값을 찾을 것이다.
모든 동전들을 비교할때 각각의 코인의 종류로 비교를 하면서 더 최소값인 녀석들 선택하는 방법을 고를 것이다.
예제의 경우 동전이 1
5
12
로 주어져 있고, 15의 가치를 만들어내는 것이 우리의 목표이다.
DP에는 우리가 만들어 하고 싶은 동전의 값을 의미한다.
우선은 1
만으로 15까지 만들어내는 경우를 정리하면 아래와 같다.
https://apption.co/embeds/jdp071
그 다음은 1
과 5
로 만들어내는 경우를 생각해 볼 차례이다.
DP[6]을 구하는 경우 우리는 두 가지를 생각해 낼 수 있다. 기존의 DP[6]의 값(1원짜리 6개 사용)과 DP[1] + 1(기존의 1원을 만들어내기 위해 필요한 동전개수 + 5원짜리 1개) 두 방법이 있고 우리는 이 두 녀석 중 최소값을 찾으면 된다.
$$ DP[i] = min(DP[i], DP[i-(동전)]+1) $$
따라서 1
또는 5
를 사용하여 만들어내는 경우를 정리하면 아래와 같다.
https://apption.co/embeds/jdp071
1
5
12
를 이용하여 만들어내면 아래와 같다
https://apption.co/embeds/jdp071
마지막 DP[15]의 경우 DP[15-12] + 1 = 3 + 1 = 4로 생각할 수 있지만! 우리는 위에서 우리가 적용해야할 점화식을 구했었다.
$$ DP[15] = min(DP[15],DP[15-12]+1) $$