2와 5로만
동전 개수가 최소가 되도록
출력할 것 : 거스름돈이 n일 때, 최소 동전의 개수
13원일 때, 5원 1개 + 2원 4개 = 총 5개가 된다
방법이 없으면 -1 출력
n = 13
money = [2, 5]
ans = 0
while n>0:
### 이런식으로 병렬로 처리하자
if n // 5 > 0: # n을 5로 나눌 수 있을 때
ans = ans + (n // 5) - 모든 경우의 수를 해볼 수 있도록 변수하나 생성해주자
n = n % 5
if n // 2 > 0:
ans += n // 2
n = n % 2
if n == 0:
break
else:
n = 13 # 모든 경우의 수 해볼 수 있도록 원상복구 시켜주기
m : 원래대로 돌릴 수 있도록하는 정답값 원본
stopword : 0,1,3은 어떻게 해도 안나오는 값이므로 미리 전처리
minus : 처음에 5로 빼보고 안되면 5 하나씩 빼면서 모든 경우의 수 해볼 수 있게
n = int(input())
m = n
money = [2, 5]
ans = 0
stopword = [0,1,3]
minus = 0
while n>=0:
if n in stopword:
ans = -1
break
if n // 5 > 0:
ans += (n // 5) - minus
n = (n % 5) + (minus * 5)
if n // 2 > 0:
ans += (n // 2)
n = n % 2
if n == 0:
break
elif n > 0:
n = m
ans = 0
minus += 1
print(ans)
import sys
input = sys.stdin.readline
n = int(input())
dp = [-1] * (n+8)
dp[2]=1
dp[4]=2
dp[5]=1
dp[6]=3
dp[7]=2
dp[8]=4
for i in range(9, n+1):
dp[i] = min(dp[i-2], dp[i-5])+1
print(dp[n])
n = int(input())
cnt = 0
i = 0
while True:
if n % 5 == 0: # 5의배수이면 or 2로만 거슬러주고 n이 0이된경우
cnt += n//5 #5로나눈 몫이 정답 - 끝!
break
else:
n -= 2 #5의배수가 아니면 2백원씩 뺴면서 5로 나누어떨어지는것이 나오도록
cnt += 1
if n < 0: # 2백원씩 뺏더니 음수가 되버린경우 --> 거슬러줄수 없을을 의미함
break
print(-1) if n < 0 else print(cnt)