Jinho Tech

기본적인 다이나믹 프로그래밍 문제이다.

n = int(input())
dp = [-1]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    if i >= 2 and dp[i-2] > -1:
        dp[i] = (dp[i-2]+1) if dp[i] == -1 else min(dp[i-2]+1, dp[i])
    if i >= 5 and dp[i-5] > -1:
        dp[i] = (dp[i-5]+1) if dp[i] == -1 else min(dp[i-5]+1, dp[i])
print(dp[n])

11047번 동전 0과 거의 똑같은 문제이다.

거스름돈보다 싼 동전 중에서 제일 큰 것부터 순서대로 꽉꽉 채운다는 느낌으로 풀면 된다.

change = 1000 - int(input())
cnt = 0
for c in [500, 100, 50, 10, 5, 1]:
    if c <= change:
        cnt += change//c
        change %= c
    if change == 0:
        break
print(cnt)