BOJ 2294 동전 2

문제

접근 방법

얼핏보면 가치가 큰 동전부터 넣으면 동전의 개수가 최소가 되는 그리디 문제라고 생각할 수 있지만 이에 해당되는 경우는 동전 가치들이 서로 배수의 관계에 있을 때만 해당된다.

이 때는 모든 경우의 수를 고려해야 풀 수 있다. 하지만 모든 경우의 수를 고려하게 되면 너무 많은 경우의 수가 생긴다. 이럴 때, 다이나믹 프로그래밍을 사용하면 된다고 생각했다.

list의 index를 동전들의 가치라고 하고 각 코인 가치를 coin이라고 할 때 다음 점화식으로 이 문제를 해결할 수 있음을 떠올렸다.

\[dp[n] = dp[n-coin] + 1\]

정답 코드

import sys
input = sys.stdin.readline


"""
list의 index를 동전들의 가치라고 하고 각 코인 가치를 coin이라고 할 때 
list의 값은 index 만큼의 가치를 만들기 위한 최소 동전 개수라고 설정
"""
n,k = map(int, input().split())
coins = []
for _ in range(n):
  c = int(input())
  # 코인의 가치가 너무 크면 dp[c] = 1으로 인해 index error가 발생할 수 있음
  if c > k:
    continue
  coins.append(c)

#가치가 같은 동전이 여러번 주어질 수 있으므로 set를 적용함
coins = list(set(coins))

dp = [int(1e9)]*(k+1)

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

if dp[k] == int(1e9):
  print(-1)
else:
  print(dp[k])