[백준/Python] #17212 달나라 토끼를 위한 구매대금 지불 도우미

문제

 

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

---

Algorithm

토끼는 1,2,5,7원의 동전을 가지고 최소의 개수로 해당 가격을 딱 맞추어서 내야한다.

예를 들어 23원이라고 해보자. 23원을 완성하는 경우의 수는 여러가지가 있지만 이를

23 = 7 + 16원을 만들기 위한 동전개수 = 5 + 18원을 만들기 위한 동전개수 = 2 + 21원을 만들기 위한 동전개수 = 22 + 1원을 만들기 위한 동전 개수가 된다. 

즉 N(N>7)원에 대하여 N원을 지불하기 위해 필요한 최소 동전 개수는 min(N-1, N-2. N-5, N-7) + 1개이다.

dp배열을 만들고, dp[0] = 0로 기준을 잡아서 반복문을 돌린다.

해당 가격에 대해 1,2,5,7원을 뺀 값의 동전 개수를 확인하여 이중에 최솟값을 dp배열에 저장해준다. 이때, 음수가격은 존재하지 않으므로 조건문으로 처리해 주었다.

---

 

 

Code

input = __import__('sys').stdin.readline

n = int(input())
dp = [0 for _ in range(n+1)]

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

print(dp[n])