[백준 파이썬] 2294 동전 2

 

2294번: 동전 2

문제



 

주어진 동전의 종류를 이용해 최소한의 개수로 원하는 숫자를 만드는 문제이다.

---

풀이

Dp배열을 생성 후 N의 숫자를 만들 때 필요한 동전의 최소값을 Dp[N]에 저장하는 방법을 사용하여 해결하였다.

 

coin = []
for i in range(n):
    coin.append(int(input()))

dp = [sys.maxsize] * (k + 1)
dp[0] = 0

동전의 종류를 입력받고 dp배열을 초기화한다.

이 때 0을 만드는 경우의 수는 없으므로 dp[0]값은 0으로 초기화 한다.

 

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

 

 

이 후 동전의 종류별로 배열을 순회한다.

만약 N을 만들어야 하고 동전의 종류가 a, b, c일 때

dp[n-a], dp[n-b], dp[n-c] 중 가장 작은 값을 고른 후 +1을 해준 값이 N을 만들기 위한 최소 동전의 개수가 된다.

 

if dp[k] == sys.maxsize:
    print(-1)
else:
    print(dp[k])

 

마지막으로 dp값이 처음 초기화해준 값과 일치하다면 값을 만들 수 없으므로 -1을 출력하고

아니라면 값을 출력한다.

 

코드

import sys
n, k = map(int, input().split())

coin = []
for i in range(n):
    coin.append(int(input()))

dp = [sys.maxsize] * (k + 1)
dp[0] = 0

for c in coin:
    for i in range(c, k + 1):
        if dp[i] > 0:
            dp[i] = min(dp[i], dp[i - c] + 1)
    
if dp[k] == sys.maxsize:
    print(-1)
else:
    print(dp[k])