[BOJ] 2294 - 동전 2

[BOJ] 2294 - 동전 2

문제

문제

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

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

입력

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

출력

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

예제 입력

3 15
1
5
12

예제 출력

3

문제 해결

동전의 최소 개수를 출력하는 것이다. dp 배열을 만들어서 해당 동전 가치를 만드는데 필요한 동전의 최소 개수를 담았다.

1. 1 부터 k 까지 i로 돌면서 내부적으로 동전의 가치를 순회한다.
2. 동전의 가치를 순회하면서 동전의 가치보다 i가 크다면 dp[i - 동전의 가치] 의 값을 가져온다.
3. 그중 가장 작은 값을 가져와 해당 값 + 1 한 값을 dp[i]에 넣은다.

2번과 같은 동작을 생각한 이유는 예를 들어서 8원의 가치를 만드는 최소개수를 구하는데 주어진 동전의 가치가 1, 3, 5 라면 8을 만드는 가지수는 7원을 만드는 방법에 1원을 더하는 방법, 5원을 만드는 가치에 3원을 더하는 방법, 3원을 만드는 방법에 5원을 더하는 방법 따라서 7원, 5원, 3원을 만드는 것중 최소 개수에 +1 한 값이 8원을 만드는 최소 개수이다.

python 코드

n, k = map(int, input().split())
dp = [0] * (k+1)
answer = []
for _ in range(n):
    answer.append(int(input()))
for i in range(1, k+1):
    min_num = -2
    for el in answer:
        if i >= el:
            if min_num == -2 or min_num > dp[i-el]:
                if dp[i-el] != -1:
                    min_num = dp[i-el] 
    dp[i] = min_num+1

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

느낀점

문제를 해결할 수 있는 방법은 바로 생각이 나는 문제였지만, 특정 조건인 -1 을 출력하는 것이 도금 어려웠다.