[python/파이썬] 백준 17212 달나라 토끼를 위한 구매대금 지불 도우미

[문제 출처]

https://www.acmicpc.net/problem/17212

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

 

[문제 풀이]

1,2,5,7원짜리 동전들을 이용하여 최소 개수의 동전을 사용하는 경우의 동전 개수를 구하는 문제이다.

우선 1원짜리 i원은 i개의 동전으로 지불할 수 있다. 따라서 리스트를 i로 초기화한다.

후에 1,2,5,7원 적은 경우 중에 어떤 경우가 가장 적은 동전을 사용했는지 판단하고 그 경우 +1을 dp[n]으로 정한다.

import sys
input = sys.stdin.readline

n = int(input())

dp = [e for e in range(n+1)]

for i in range(2,n+1):
    dp[i] = dp[i-1] + 1
    if i >= 2:
        dp[i] = min(dp[i], dp[i-2]+1)
    if i >= 5:
        dp[i] = min(dp[i], dp[i-5]+1)
    if i >= 7:
        dp[i] = min(dp[i], dp[i-7]+1)

print(dp[n])