https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
www.acmicpc.net
DP문제는 계속 풀어도 어렵네요...
<코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
n, k = map(int, input().split())
coin = []
p = [10001 for _ in range(k + 1)]
p[0] = 0
for _ in range(n):
coin.append(int(input()))
for i in range(n):
for c in range(coin[i], k + 1):
if p[c] > p[c - coin[i]] + 1:
p[c] = p[c - coin[i]] + 1
if p[k] == 10001:
print(-1)
else:
print(p[k])
|
cs |
coin : input 동전의 가치 리스트
p : DP 테이블
p[c]에는 c만큼의 가치를 만들기 위해 필요한 동전의 최소 개수를 저장합니다.
목표 가치인 k를 만들기 위해 사용된 동전의 최소 개수는 p[k]에 저장될 것입니다.
p[k]가 업데이트 되지 않았다면(10001 이라면) 주어진 동전으로 k 가치를 만들지 못함을 의미합니다.
728x90
'난 이 분야 전문가야! > Algorithm' 카테고리의 다른 글
| 프로그래머스 :: 크레인 인형뽑기 - python 풀이공유 (0) | 2020.07.13 |
|---|---|
| [백준][C] 17070 파이프 옮기기 1 - 풀이 공유 (0) | 2020.05.04 |
| [백준][Python] 1915 가장 큰 정사각형 - 풀이 공유 (0) | 2020.04.30 |
| [백준][C] 2994 내한 공연 - 풀이 공유 (1) | 2020.04.28 |
| [백준][Python] 2960 에라토스테네스의 체 - 풀이 공유 (0) | 2020.04.19 |