[백준/Python(파이썬)] 2294 동전 2

문제

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

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

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이

2293번 동전 1과 유사한 문제. 사용한 동전의 최대 개수, 최소 개수를 구해야 하는 부분이 다르다.

dp 배열 값을 0번째 값을 제외하고 최대값이 100,001로 초기화한다.

값이 1, 5, 12인 동전을 사용할 때

우선 1원 짜리만 사용하는 경우부터 시작해서 15까지 1, 2, 3, ..., 15 로 dp값을 변경한다.

5원 짜리를 포함해서 구하게되면 dp[5] = min(dp[5-5]+1, dp[5]) = min(1, 100001) 때문에 1로 변경된다.

그 후부터 계속 dp[6] = min(dp[6-5]+1, dp[6]) = min(dp[1]+1=2, 100001)) 처럼 5가 포함된 경우의 수로 계산된다.

12도 마찬가지로 dp값을 갱신한다.

p[15] = min(dp[15-5]+1, 100001)) = dp[10]+1 = 2+1 = 3  (10=5+5)

주어진 동전으로 k원을 만들 수 없는 경우, dp의 초기값인 100001에서 값이 변경되지 않았으므로 마지막에 조건문을 통해 -1을 출력하도록 한다.

소스코드

n, k = map(int, input().split())  # n: 동전의 종류, k: 가치의 합
c = []
for i in range(n):
    c.append(int(input()))
dp = [0] + [100001 for _ in range(k)]

for i in c:
    for j in range(1, k+1):
        if j - i >= 0:
            dp[j] = min(dp[j-i]+1, dp[j])
if dp[k] != 100001:
    print(dp[k])
else:
    print(-1)

Git : github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_2294.py

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