[백준 2294번] 동전 2 (python)

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

기록

(dp 8일차) 갑자기 하기 싫어서 대충하다가 별 에러 다 났다.

 

풀이는 n을 만들 수 있는 최소 동전개수 dp배열을 만들어, dp[n] = min(dp[i], dp[i-1원]+1, dp[i-5원]+1, dp[i-10원]+1, , ,) 이런 식으로 모든 동전을 추가해보며 최솟값을 찾아 dp를 갱신한다.

 

코드

from sys import stdin

n, k = map(int, stdin.readline().split())
coins = [int(stdin.readline()) for i in range(n)]

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

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

1. n을 만들 수 있는 최소 동전개수 dp배열을 생성한다. 최솟값을 찾기 위해 기본 1e9로, 0번째는 0으로 초기화하였다.

2. n을 순차적으로 돌며 각 동전을 사용했을 때의 동전 개수를 비교해보며 최솟값을 갱신한다.

3. k를 만들 수 있는 최소 동전개수를 dp에서 반환한다. 1e9일 시 만들 수 없는 수이다.