BOJ 14916번 거스름돈 파이썬

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

n이 9인 경우까지 답을 뽑아보고, n이 홀수면 n-1의 값 -1이고, 짝수면 n-1의 값 +2 인줄 알았는데 아니었다.

n이 10을 넘어서면부터 n-1의 답 +2가 답이 아니게 되기 때문이다. (5원을 2개주면 되기 때문에)

그래서 10을 넘어서 계속 계산해보다가, 생각해보니 2원이랑 5원으로만 계산해줄 수 있으니, n>10이라면 n-2값 의 답 +1이 답이고, n≥10일때는 n-5의 값 +1 이 답이라는 결론에 도달했다.

1: -1
2: 1
3: -1
4: 2
5: 1
6: 3
7: 2
8: 4
9: 3

10 이후부터가 분기점

10:2
11:4
12:3
13:5
14:4
15:3

n = int(input())
dp = [0,-1,1,-1, 2 ,1]

if n < 6:
    print(dp[n])

else:
    for i in range(6,n+1):
        if i < 10:
            dp.append(dp[i-2]+1)
        else:
            dp.append(dp[i-5]+1)

    print(dp[n])