7579번 앱

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

dp 다이나믹 동적 계획 dfs 이분 탐색 파라메트릭 서치 cache 캐시 boj 복습 필수 추천 코테 코딩 냅색

다시 풀어볼만한 문제이다.(knapsack(dp) + 파라메트릭 서치)

cost(비용)을 파라메트릭 서치의 변수로 활용한다.

첨부한 코드의 29번 째 줄에서 min이 아니라 max인 이유는 정해지고 고정된 cost로 최대한 많은 양을 담도록(m 이상이 되게) 해야하기 때문이다.

dp[a][b] = c → a번 째 앱에 대한 것과 a번 째 앱까지의 비용(b)을 써서 최대 c만큼의 용량을 나타낸다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 101
#define INF 2e9;
 
int n, m, cache[Max][Max * Max];
vector<pair<int, int> > v;
 
int dfs(int idx, int cost)
{
    if (idx == n) {
        return 0;
    }
 
    int &ret = cache[idx][cost];
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    if (v[idx].first <= cost) {
        ret = dfs(idx + 1, cost - v[idx].first) + v[idx].second;
    }
 
    // 최대한 많은 양을 담는다
    ret = max(ret, dfs(idx + 1, cost));
 
    return ret;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d", &n, &m);
 
    int cap;
    for (int i = 0; i < n; i++) {
        scanf("%d", &cap);
        v.push_back({ 0, cap });
    }
 
    int money, Right = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &money);
        v[i].first = money;
        Right = max(Right, money);
    }
 
    int Left = 0, answer = INF;
    Right *= n;
 
    while (Left <= Right)
    {
        memset(cache, -1, sizeof(cache));
 
        int mid = (Left + Right) / 2;
 
        if (dfs(0, mid) >= m) {
            //printf("g = %d, mid = %d\n", g, mid);
            answer = min(answer, mid);
            Right = mid - 1;
        }
        else {
            Left = mid + 1;
        }
    }
 
    printf("%d\n", answer);
 
    return 0;
}