[LeetCode] 322. Coin Change (C++)

문제

https://leetcode.com/problems/coin-change/

Coin Change - LeetCode

 

풀이

 

난이도: Medium 

 

유명한 다이나믹 프로그래밍 문제.

 

처음 풀면은 그리디 방식으로 가장 높은 동전 순서대로 amount값을 만들어 가기 쉽다.

하지만 동전이 [1, 4, 6]로 있을 때 14를 만들어야 된다고 생각해보자.

가장 높은 동전인 6을 먼저  2개 사용하면 나머지 2는 1의 동전 2개로 만들어 총 4개의 동전이 필요하다.

하지만 정답은 6 + 4 + 4 = 14로 6의 동전 1개, 4의 동전 2개로 3개의 동전으로 14를 만들 수 있다.

따라서 그리디가 아닌 모든 경우를 확인해보는 DP방식으로 해결해야 한다.

 

DP의 구현은 간단히 아래와 같은 점화식으로 value의 값을 구성하는 동전의 최소 개수 구현할 수 있다.

dp[value] = min(dp[value], dp[value - coins종류] +1);

 

 

코드