[백준] 2294 - 동전 2

백준 2294번 동전 2

 

➡️문제 링크 : https://www.acmicpc.net/problem/2294

 

DP 에 관해 잘 알지 못하는 것 같아서 DP 문제 리스트를 풀던 중에 실버도 웬만큼 해봤다 싶어 골드에 도전해보기로 했다. 

k 만큼의 길이를 dp로 해서 dp[i] 는 i 만큼의 가격이 가질 수 있는 동전의 최소 개수를 의미하는 것으로 문제를 푸는 거라고 생각은 했지만 어떻게 '겹치는 소문제' 구조를 만들 수 있을지 생각하기 어려웠다. 

그래서 다른 블로그를 참고했고, 이전의 dp 값을 이용하는 것이 바로 이전의 값만 이용하지 않아도 점화식의 형태를 갖고 있으면 된다는 사실을 알 수 있었다. 사소한 발견이지만, dp에 대한 이해의 범위가 넓어졌다고 생각해 이렇게 블로그에 남기기로 했다.

 

➡️참고한 블로그 링크 : https://velog.io/@grace0st/%EB%8F%99%EC%A0%842-%EB%B0%B1%EC%A4%80-2294%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC

동전2 (백준 2294번 파이썬)

 

참고한 블로그 링크는 다음과 같으며, dp[0]을 0으로 초기화한 후, 값을 늘려가며 i를 정하고, coins를 순회하며 i-coin이 0보다 큰 값이라면 dp에 dp[i-coin]+1과 dp[i] 값을 비교하여 더 작은 값을 저장하는 방식으로 진행하였다. 

 

코드 

# DP
import sys

input = sys.stdin.readline

n,k=map(int,input().split(' '))

coins = [int(input()) for _ in range(n)]
inf=10**6
dp=[inf 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[k]==inf:
    print(-1)
else:
    print(dp[k])