My code
n,m = map(int,input().split())
array = []
for i in range(n):
array.append(int(input()))
d = [10001] * (m + 1)
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
Answer
n,m = map(int,input().split())
array = []
for i in range(n):
array.append(int(input()))
d = [10001] * (m + 1)
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001:
d[j] = min(d[j], d[j - array[i]] + 1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
Code Review
이번 문제는 N 가지 종류의 화폐가 있을 때 최소한의 화폐를 사용해서 M 원이 되도록 만드는 것이었습니다. 이 문제의 점화식을 먼저 써보자면
-a(i) = min[a(i), a(i-k) + 1]
입니다. 예를 들어, 만약 7원이 되도록 만들고 싶고 화폐의 종류가 2, 3, 5원일 때 앞의 경우는 모두 이미 구했다 가정하면 7원이 되도록 마지막에 2 또는 3 또는 5 를 더할 수 있습니다. 즉, 5원이 되도록 하는 화폐의 최소 개수를 이미 구했다면 마지막에 2를 더해주면 되고 4원이 되도록 하는 화폐의 최소 개수를 이미 구했다면 마지막에 3을 더해주면 되고 2원이 되도록 하는 화폐의 최소 개수를 이미 구했다면 마지막에 5를 더해주면 됩니다. 따라서 7에서 2 또는 3 또는 5 를 뺀 수에서 현재까지 구한 화폐의 최소 개수에 1을 더해주면 필요한 화폐의 개수를 알 수 있습니다. 이것을 현재까지 구해 둔 값과 비교하여 더 작은 값을 선택하도록 해주면 됩니다.
따라서 반복문을 사용하여 0~m 까지 모든 금액마다 필요한 화폐 개수를 계산해주었고 점화식을 이용해 최소 개수로 갱신해주었습니다.
만약 d[m] 의 값이 10001 이라면 만들 수 없는 금액이므로 -1을 출력해주고 그렇지 않다면 d[m] 을 출력해주어 필요한 최소 화폐 개수를 출력해주었습니다.
댓글