Algorithm/BOJ
동전 2 - 2294
jhg0406
2020. 3. 1. 16:49
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
//2293 - 동전 2
//슬라이딩 윈도우 최적화
#include <iostream>
using namespace std;
#define INF 100000
int N, K;
int arr[100];
int cache[10001];
void init()
{
cin >> N >> K;
for (int i = 0; i < N; ++i)
cin >> arr[i];
for (int i = 0; i <= K; ++i)
cache[i] = INF;
cache[0] = 0;
}
int dp(int cost)
{
if (cost < 0)
return INF;
return cache[cost];
}
int main()
{
init();
for (int i = 0; i < N; ++i)
for (int cost = 1; cost <= K; ++cost)
cache[cost] = min(cache[cost], dp(cost - arr[i]) + 1);
if(cache[K] == INF)
cout << -1;
else
cout << cache[K];
}
|
cs |
https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
www.acmicpc.net
동전 2
dp문제
C(idx, cost) : 0-idx까지의 동전을 사용했을때, 가장 적은 동전을 사용해 cost를 만들었을 때 동전의 개수
C(idx, cost) = min( C(idx-1, cost) , C(idx, cost - d[idx] )
https://onedaycoding.tistory.com/77
동전 1 - 2293
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 //2293 - 동전 1 //슬라이딩 윈도우 최적화 #include using namespace std; int N, K; int arr[100]; in..
onedaycoding.tistory.com
위 링크의 최적화를 똑같이 적용했습니다.
