반응형
문제 : 백준 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);
구현
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<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);
}
|
cs |
'ps연습장' 카테고리의 다른 글
백준 7562번 : 나이트의 이동 (C/C++) (0) | 2023.09.16 |
---|---|
백준 13305번 : 주유소 풀이 (C/C++) (0) | 2023.09.15 |
백준 15649번 N과 M (1) 풀이 (C/C++) (0) | 2023.09.15 |
백준 28297번 : 차량 모듈 제작(C/C++) (0) | 2023.07.02 |
백준 28257번 : 알록달록 초콜릿 만들기(C/C++) (0) | 2023.06.30 |