문제
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])
