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

 

문제 풀이: 해당 문제는 동적 계획 알고리즘을 이용해서 풀면 된다.

거스름돈을 1원부터 총거스름돈의 액수까지 1씩 증가시키고 각각의 상황에서 2원과 5원을 썼을 때 거스름돈이 최소인 경우를 구하고 거슬러 줄 수 없으면 -1을 출력하면 된다.

예를 들어 거스름돈이 13원인 경우를 보자 처음에 2원짜리 동전을 사용하면 동전을 다 거슬러주지 못하는 상황이 발생한다. 다음으로 5원을 사용하는 경우, 이전에 거스름돈이 8원이었을 때(c [13-5] = c [8], c [8] = 4), 2원짜리 동전 4개 사용됨. 여기에 5원짜리 동전 한 개를 추가하면 13원이 된다.

money = int(input())
m = [2, 5]
max = 1000000
c = [max] * (money + 1)
c[0] = 0
for i in m:
    for j in range(1, money + 1):
        if i <= j and c[j - i] + 1 < c[j]:
            c[j] = c[j - i] + 1
if c[money] == max:
    print(-1)
else:
    print(c[money])