[BOJ] 백준 14916번 - 거스름돈(with Java)

알고리즘

문제에서 궁극적으로 구하고자 하는 답은 거스름돈 N이 주어질 때, 거슬러주는 동전의 최소 개수이다.

따라서 다른 DP 문제들과 마찬가지로 N 이하에서의 DP 값을 모두 알아야만 한다.

 

이 문제에서 알아둬야할 부분은 '손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다' 이다.

다시 말해서 2원 또는 5원으로 거슬러줄 수 없는 경우가 존재한다는 뜻이며, 이 경우에는 -1을 넣어줘야만 한다.

 

dp[0]을 구해보자. dp[0]은 거스름돈 0이 주어질 때, 거슬러주는 동전의 최소 개수이다.

하지만 거스름돈이 0이라면 거슬러줄 필요가 없으므로 거슬러주는 동전의 최소 개수는 0, 즉 dp[0] = 0이다.

dp[1]은 거스름돈 1이 주어질 때, 거슬러주는 동전의 최소 개수이다.

거스름돈이 1인 경우에는 2원짜리 또는 5원짜리로 거슬러줄 수 없으므로 dp[1] = -1이다.

dp[2]은 거스름돈 2이 주어질 때, 거슬러주는 동전의 최소 개수이다.

거스름돈이 2인 경우에는 2원짜리로 거슬러줄 수 있으므로 dp[2] = 1이다.

dp[5]는 거스름돈 5가 주어질 때, 거슬러주는 동전의 최소 개수이다.

거스름돈이 5인 경우에는 5원짜리로 거슬러줄 수 있으므로 dp[5] = 1이다.

 

이번에는 dp[4]를 구해보자. dp[4]는 거스름돈 4가 주어질 때, 거슬러주는 동전의 최소 개수이다.

거스름돈이 4인 경우에는 2원짜리 2개로 거슬러줄 수 있으므로 dp[4] = 2이다. 여기서 생각을 해보자.

거스름돈이 2인 경우에 동전을 최소로 거슬러주는 개수는 1이었기 때문에 dp[2] = 1이었다.

그렇다면 거스름돈이 4인 경우는, 거스름돈이 2일 때 거슬러주는 동전의 최소 개수 + 2원짜리 동전 1개로 볼 수 있다.

위의 말이 맞다고 가정하고 다시 구해보면 dp[4] = dp[4-2] + 1이 성립한다.

 

마지막으로 dp[10]을 구해보자. dp[10]은 거스름돈 10이 주어질 때, 거슬러주는 동전의 최소 개수이다.

거스름돈이 10인 경우에는 2원짜리 5개 또는 5원짜리 2개로 거슬러주는 2가지 경우가 존재한다.

하지만 동전의 개수가 최소가 되도록 하려면 5원짜리 2개로 거슬러주는 것이 바람직하다.

따라서 dp[10] = 2가 성립한다.

 

dp[10]에 대해서 식을 세워보도록 하자.

거스름돈이 10인 경우는, 거스름돈이 5일 때 거슬러주는 동전의 최소 개수 + 5원짜리 동전 1개인 경우와 거스름돈이 8일 때 거슬러주는 동전의 최소 개수 + 2원짜리 동전 1개인 경우로 나눠볼 수 있다.

여기서 동전의 개수를 최소가 되도록 만들려면 두 가지의 경우를 비교해서 값이 최소인 경우를 택하면 된다.

따라서 dp[10] = min(dp[10-5] + 1, dp[10-2] + 1)이 성립하는 것을 알 수 있다.

거스름돈이 10 이상인 경우에 대해서도 똑같이 식을 세워주면 점화식을 도출할 수 있다.

소스코드

문제링크

14916번: 거스름돈