문제
접근
DP 문제이다.
동전의 개수 x 구하고자 하는 K만큼의 배열을 할당해준다.
DP(i, j) = i번째 동전까지를 사용했을 때, j원을 만드는 동전의 최소 개수이다.
DP는 처음에 큰 값(나의 경우는 inf를 이용)으로 초기화해준다.
동전의 가장 작은 단위가 1원이 아닐 수도 있다.
동전을 정렬한 후 가장 작은 단위에 대해서 먼저 DP를 채워준다.
예를 들어 가장 작은 단위의 동전이 2원인 경우, 2,4,6,8…단위로 나가면서 DP를 업데이트한다.
그럼 DP(0, j)는 0 inf 1 inf 2 inf 3 inf … 이런 식으로 업데이트 될 것이다.
그 후 DP(i, j)를 순서대로 돌면서 업데이트 해준다.
j원을 만들 때 현재 동전보다 이전 단위의 동전까지만 이용한 경우, 즉 DP(i-1, j)의 값을 그대로 쓸지 아니면,
현재 동전을 사용해서 이 경우는 현재 동전의 단위가 x라고 했을 때 DP(i, j-x) + 1을 이용하면 된다.
즉 현재 동전을 하나 사용했을 때와 비교해서 작은 값을 취하면 된다.
최종적으로 모든 동전을 사용해서 k를 만든 값, DP(n-1, k)가 정답이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n, k = map(int, input().split())
money = [int(input()) for _ in range(n)]
money.sort()
dp = [[float('inf')]*(k+1) for _ in range(n)]
cnt = 0
for i in range(0, k+1, money[0]):
dp[0][i] = cnt
cnt += 1
for i in range(1, n):
dp[i][0] = 0
for j in range(1, k+1):
if j >= money[i]:
dp[i][j] = min(dp[i-1][j], dp[i][j - money[i]] + 1)
else:
dp[i][j] = dp[i-1][j]
if dp[n-1][k] == float('inf'):
print(-1)
else:
print(dp[n-1][k])