[BOJ] Q2294 동전 2

[BOJ] Q2294 동전 2

Question

Language: Python

Difficulty: Gold 5

주어진 동전의 종류를 활용해서 k원을 만들고자 할때, k원을 만들기 위해 사용되는 최소 동전 개수는?

문제의 예저를 통해서 알아보자

1	2	3	4	5	6	7	8	9	10
1	1(2)	2(2+1)	2(2+2)	5(1)	2(5+1)	2(5+2)	3(5+2+1)	3(5+2+2)	2(5+5)

6원을 만들때의 경우를 보자 5원에서 1을 추가하면 6 4원에서 2을 추가하면 6 1원에서 5을 추가하면 6

즉, 1,4,5원을 만드는 경우 중에서 제일 적은 동전의 개수를 활용하는 경우를 구해서 해당 값에 1을 추가하면 6원을 만드는 최소 동전 개수를 구할 수 있다.

이 경우, 5원을 만드는 경우가 1가지로 제일 적으므로, 6원을 만드는 최소 동전의 개수는 2개이다.

각각 k 원에 대해 아래의 DP 연산을 진행하면 된다.

Logic

for i in range(k):
  min_counts=inf
  for money_type in money_types:
    if i-money_type >=0:
      min(min_counts,dp[i-money_type])
    dp[i]=min_counts+1

Solution

from math import inf
def solution():
    dp=[-1] * (k+1)
    dp[0]=0
    
    if k < min(money_types):
        print(-1)
        exit(0)
        
    for i in range(1,k+1):
        temp=inf
        for money_type in money_types:
            prev_step=i-money_type
            if prev_step>=0:
                temp=min(temp,dp[prev_step])

        dp[i]=temp+1
        
    if dp[i]==inf:
        print(-1)
    else:
        print(dp[k]) 
    
if __name__ =="__main__":
    n,k=map(int,input().split())
    money_types=[]
    for _ in range(n):
        money_types.append(int(input().strip()))
    solution()