[백준/파이썬] 2294 : 동전 2

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

2294번: 동전 2

문제 요약 : n가지 동전으로 k원을 만든다. 사용한 동전의 최소의 개수를 출력하고 불가능할 경우 -1을 출력한다.

 

 

어쩌다보니 동전문제 도장깨기 중이다..ㅋㅋ

이렇게 된김에 계속 동전 시리즈를 풀어보겠음

 

시도 1 )

앞서 동전문제를 많이 풀어서 그런지 금방 규칙이 눈에 보였다.

그냥 동전 1문제와 큰 틀은 같다.

 

동전 1 풀이는 아래와 같음

https://eunsun-zizone-zzang.tistory.com/15

[백준/파이썬] 동전 1

 

예시인 1,5,12로 15를 만드는 최소값을 출력해보겠다.

 

먼저 coins에서 하나씩 꺼내면 제일 작은 1부터 시작된다.

dp[i]는 i원을 만드는데 필요한 동전의 개수이다.

최소값을 구해줘야하기 때문에 최대 동전의 가치라고 문제에 주어진 수보다 큰 숫자를 넣어줬다.(그래야 최솟값비교가능)

 

1원만 가지고 i원을 만들 때에는 i개의 동전이 필요하다.

 

1원과 5원을 가지고 i원을 만들 때에는 일단, dp[5]부터 시작할 수 있다.

 

1+1+1+1+1과 5를 비교해보면 당연히 하나만 사용하는 5가 더 크다.

동전 1과 마찬가지로, dp[i-coin]에 5원 하나를 추가해주는 경우 인것을 알 수 있다.

그러나 무조건 dp[i-coin]+1한 값이 최소가 아닐 수 있기 때문에 min을 사용하여 dp값을 갱신해준다.

 

처음에 문제를 풀었는데도 92%에서 틀렸습니다가 떠서 뭐가 문젠지 한참을 고민했는데,

마지막에 목표값을 가진 동전들로 만들 수 없을 경우 -1을 출력해줘야하는것을 빼먹어서 생긴 일이었다.

 

문제를 제대로 읽자!!

n,k = map(int,input().split())
coins = list(int(input()) for _ in range(n))
dp = [100001]*(k+1)
dp[0] = 0

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

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