동전 2 [백준 2294] - python

 

import sys
input = sys.stdin.readline

def BOJ2294() :
  n, k = map(int, input().split())
  coins = []
  for _ in range(n) :
    coins.append(int(input().strip()))

  dp = [1e6 for _ in range(k+1)]
  dp[0] = 0

  for i in range(1, k + 1) :
    for coin in coins :
      if i - coin >= 0 :
        dp[i] = min(dp[i], dp[i-coin] + 1)

  if dp[-1] == 1e6 :
    print(-1)
  else :
    print(dp[-1])
BOJ2294()

 

접근 방법 :

1. 입력받은 가치를 만들어 낼 수 있는 동전의 최소개수를 구하는 문제입니다.

2. 15를 1로 15개 vs 1 * 3 + 12 vs 5 * 3 의 개수들을 비교해야 한다는 뜻이 됩니다.

3. 2번에 착안하여 dp를 이용하여야 합니다. 

4. 매 index에서 동전의 가치를 뺀 인덱스에서 + 1 을 한것과 현재 입력되어 있는 값의 대소 비교를 해주면 문제를 해결할 수 있습니다.

 

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

2294번: 동전 2