백준 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 (JAVA)

 

문제 해석

 

1원, 2원, 5원, 7원 동전을 보유하고 있다. 

지불해야 하는 금액이 입력값으로 주어지고 해당 금액을 보유한 동전들을 이용해서 지불해야 한다.

단 동전 개수를 최소화하여 지불한다.

 

알고리즘

 

보유하고 있는 동전이 1, 2, 5, 7 이므로 

dp[n]은 dp[n-1], dp[n-2], dp[n-5], dp[n-7] 중 최소값에 1, 2, 5, 7 중 하나의 동전을 사용하여 지불하면 된다.

 

코드