forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path8.py
More file actions
22 lines (19 loc) · 689 Bytes
/
8.py
File metadata and controls
22 lines (19 loc) · 689 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
for j in range(array[i], m + 1):
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])