문제
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
출력
첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
풀이
dp문제는 참 dp인건 알겠는데 어떻게 풀어나가야할지 고민하는 시간이 너무 오래걸린다
이 문제도 여러 방법을 헤맸다
결국은 dp의 점화식들 중에서도 간단한 점화식을 이용해 풀 수 있었다
같은 가치의 코인이 여러 번 주어지는 것은 사실상 큰 의미가 없다 따라서 동전을 저장하는 리스트를 set으로 중복제거했다가 list로 다시 바꿔줬다
그리고 dp리스트의 길이는 k+1로 선언하되 모든 원소의 값이 무한대의 값을 갖도록 선언한다
이후 dp[0]을 0으로 초기화하는 것이 필요하다
for 루프를 1부터 k까지 돌게하면서 가지고 있는 코인들로 값을 만들 수 있는지 없는지를 판단하는 과정을 거치는데, 현재의 코인이 현재의 값보다 크다면 이유를 불문하고 불가능하므로 continue한다
dp는 다양한 경우에 각 단계를 목표점이라고 생각하고 문제를 접근할 때가 많은데 이 문제도 유사하다
ex) 한 번에 계단을 한 칸 혹은 두 칸 오를 수 있는 경우 목표까지 가장 적은 걸음 수로 오르는 방법 => 각 계단에 이르기까지의 최소 걸음 수는 해당 계단에서 한 칸 아래에 있는 계단까지 도달해서 한 칸을 오르는 방법과 두 칸 아래에 있는 계단까지 도달해서 한번에 두칸을 오르는 방법 중 더 적은 걸음을 한 경우를 선택하는 것이다
coin1, coin2, coin3이 존재할 때, dp[i]의 최소값은, 즉 i원이 되기까지 가장 적은 수의 동전을 사용하는 방법은 i-coin1원에서 coin1원을 더하는 경우, i-coin2원에서 coin2원을 더하는 경우, i-coin3원에서 coin3원을 더하는 경우 중 사용한 동전의 개수가 적은 경우를 선택하는 것이다
그러나, i가 coin보다는 크거나 같지만, i-coin의 경우의 수가 존재하지 않는 경우(무한대)에는 그 coin을 사용해서는 i원을 만들 수 없는 것이다
코드
import sys
n, k = map(int, sys.stdin.readline().split())
inf = float("inf")
dp = [inf]*(k+1)
dp[0] = 0
coins = list(set([int(sys.stdin.readline()) for _ in range(n)]))
for i in range(1, k+1):
for coin in coins:
if coin > i:
continue
if dp[i-coin] != inf:
dp[i] = min(dp[i], dp[i-coin]+1)
if dp[k] != inf:
print(dp[k])
else:
print(-1)