[백준] 14916번 거스름돈 파이썬 풀이

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

---

1. 접근 방식

• 다이나믹 프로그래밍과 그리디, 2가지 버전으로 접근했다.

다이나믹 프로그래밍 문제를 연습하고자 카테고리를 타고 들어온 문제였기 때문에 dp 테이블을 사용하는 다이나믹 프로그래밍 기법에 맞춰 풀이하고자 노력했다.

이후엔 그리디로도 문제를 해결해보았다. 이 문제는 dp 방식보다 그리디 방식이 더욱 빠르고 간단하다. 그리디로 작성한 코드는 3번에서 확인할 수 있다.

 

• 2원과 5원 동전만 거슬러 줄 수 있으므로, dp 테이블의 5번 인덱스까지 미리 초기화해두자.

dp 리스트에 1원 ~ 5원을 받았을 때 거슬러주는 동전 개수를 미리 초기화해둔다.

 

• 다이나믹 프로그래밍의 가장 대표 문제인 「1로 만들기」 풀이와 유사하게 접근하자.

만약 6원을 거슬러주어야 할 때를 가정하면, 6원은 ⓐ 4원에서 2원을 추가로 거슬러주든지 ⓑ 1원에서 5원을 추가로 거슬러줄 수 있다. 둘 중에서 더 적은 동전 개수를 갖는 방식으로 선택하면 된다.

즉, dp[6] = min( dp[6 - 2] + 1, dp[6 - 9] + 1)이다. 1을 더하는 이유는 2원이나 5원짜리 동전을 더해줘야 하기 때문이다. 단, 이때 dp[6 - 9] = dp[1] = -1 (거슬러줄 수 없음)이다. 이 경우에 dp[6]은 무조건 dp[6 - 2] + 1로 초기화된다.

 

 

 

2. 정답 코드

n = int(input())

dp = [0] * 100001

dp[1] = -1
dp[2] = 1
dp[3] = -1
dp[4] = 2
dp[5] = 1

for i in range(6, n + 1):
    if dp[i - 2] > 0 and dp[i - 5] > 0:
        dp[i] = min(dp[i - 2] + 1, dp[i - 5] + 1)

    elif dp[i - 2] < 0 and dp[i - 5] < 0:
        dp[i] = -1

    elif dp[i - 2] > 0:
        dp[i] = dp[i - 2] + 1

    elif dp[i - 5] > 0:
        dp[i] = dp[i - 5] + 1

print(dp[n])

 

 

 

3. 그리디 버전 코드

최대한 5원으로 거슬러주면 최소한의 동전으로 거스름돈을 줄 수 있다. 따라서 거스름돈이 5로 나뉜다면 최대한 5로 나누고, 그렇지 않다면 -2를 한 번씩 해준다.

n = int(input())
count = 0

while n > 0:
    if not n % 5:
        times = n // 5
        n -= 5 * times
        count += times

    else:
        n -= 2
        count += 1

print(count if n >= 0 else -1)