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

문제 : 백준 2294

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

풀이

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);

 

구현

 

#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
const double pi = acos(-1);
const int MOD = 1000000007;
 
typedef tuple<double, int, int> dii;
 
int N, K;
int dp[101][10101];
int cost[101];
 
int f(int n, int k){
    if(k == 0) return 0;
    if(n == 0) return INF;
 
    if(dp[n][k] != -1) return 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, -1, sizeof(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);
}