본문 바로가기
ps연습장

백준 2294번 : 동전 2 (C/C++)

by hwsyl 2023. 9. 16.
반응형

문제 : 백준 2294

https://www.acmicpc.net/problem/2294

백준 2294번 : 동전 2

풀이

dp로 풀면 된다.

필자는 아래와 같이 dp 점화식을 정의하였다.

 

dp[n][k] = f(n-1, k);
    if(k >= cost[n]) dp[n][k] = min(dp[n][k], f(n, k-cost[n])+1);

 

구현

 

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
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<intint> pii;
typedef pair<ll, ll> pll;
typedef pair<doubledouble> pdd;
typedef tuple<intintint> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 010-1 };
const int dy[] = { 10-10 };
const double pi = acos(-1);
const int MOD = 1000000007;
 
typedef tuple<doubleintint> dii;
 
int N, K;
int dp[101][10101];
int cost[101];
 
int f(int n, int k){
    if(k == 0return 0;
    if(n == 0return INF;
 
    if(dp[n][k] != -1return dp[n][k];
 
    dp[n][k] = f(n-1, k);
    if(k >= cost[n]) dp[n][k] = min(dp[n][k], f(n, k-cost[n])+1);
 
    return dp[n][k];
}
 
int main(){
    memset(dp, -1sizeof(dp));
    scanf("%d %d"&N, &K);
    for(int i = 1; i <= N; i++){
        scanf("%d"&cost[i]);
    }
    int ans = f(N, K);
    printf(ans >= INF ? "-1" : "%d", ans);
}
 
cs