[백준] 동전2

출처:: www.acmicpc.net/problem/2294

분류:: dp

 

1. 문제 이해 및 해결과정

- 문제 예시의 경우, dp[i - 1], dp[i - 5], dp[i - 12] 중 min값에 1을 더하면 된다 - dp[0]=0

 

2. 풀이방법

  1. dp

#동전2
#https://www.acmicpc.net/problem/2294
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
coin = [ int(input()) for _ in range(n)]
INF=100001 #INF라면 만들수 없는 숫자
dp=[INF]*(INF)
dp[0]=0 #꼭 필요, 0원을 만들 수 있는 방법은 0개
coin.sort()
for i in range(coin[0],k+1):
    for x in coin:
        dp[i]=min(dp[i-x]+1,dp[i])

if dp[k]==INF: #현재 가진 화폐로 만들 수 없음
    print(-1)
else:
    print(dp[k])

 

3. 오답원인

  1. 동전이 K보다 큰 값이 올 수 있음

4 15
1
5
12
100000
#3

  2. coin을 정렬해주서야한다

-> bottom-up방식으로 구현하는데 coin이 큰수부터 들어 오게 된다면 dp테이블이 꼬이게 된다

2 7
5
1
7
#답은 1인데 sort를 하지 않으면 3이 나온다 

 

4. 알게된 점