백준 14916번 거스름돈

 

못거슬러주는 경우도 고려해야해서 좀 복잡해진다.

 

import sys

n=int(sys.stdin.readline().rstrip())
v=[0]*(n+1)
if n>=2:
    v[2]=1
if n>=4:
    v[4]=2
if n>=5:
    v[5]=1
for i in range(6,n+1):
    two=v[i-2]+1
    if v[i-2]==0:
        two=0
    five=v[i-5]+1
    if v[i-5]==0:
        five=0
    v[i]=min(two,five)
    if two==0 or five==0:
        v[i]=max(two,five)
if v[n]==0:
    print(-1)
else:
    print(v[n])

 

근데 9 이후로는 거슬러주는게 불가능한 케이스가 없어서 굳이 five,two변수 사용하지않고 깔끔하게 푸는게 가능할듯하다.

물론 나는 엣지 케이스 신경쓰느라 다시풀라해도 이렇게 풀겠지만.