문제접근🤔

모든 동전들을 비교해보면서 최소값을 찾을 것이다.

모든 동전들을 비교할때 각각의 코인의 종류로 비교를 하면서 더 최소값인 녀석들 선택하는 방법을 고를 것이다.

예제의 경우 동전이 1 5 12 로 주어져 있고, 15의 가치를 만들어내는 것이 우리의 목표이다.

DP에는 우리가 만들어 하고 싶은 동전의 값을 의미한다.

우선은 1 만으로 15까지 만들어내는 경우를 정리하면 아래와 같다.

그 다음은 1 과 5 로 만들어내는 경우를 생각해 볼 차례이다.

DP[6]을 구하는 경우 우리는 두 가지를 생각해 낼 수 있다. 기존의 DP[6]의 값(1원짜리 6개 사용)과 DP[1] + 1(기존의 1원을 만들어내기 위해 필요한 동전개수 + 5원짜리 1개) 두 방법이 있고 우리는 이 두 녀석 중 최소값을 찾으면 된다.

$$ DP[i] = min(DP[i], DP[i-(동전)]+1) $$

따라서 1 또는 5 를 사용하여 만들어내는 경우를 정리하면 아래와 같다.

1 5 12 를 이용하여 만들어내면 아래와 같다

마지막 DP[15]의 경우 DP[15-12] + 1 = 3 + 1 = 4로 생각할 수 있지만! 우리는 위에서 우리가 적용해야할 점화식을 구했었다.

$$ DP[15] = min(DP[15],DP[15-12]+1) $$