[백준] [C++] 7579번 앱 (dp, knapsack, bsearch)

1. 문제

7579번: 앱 (acmicpc.net)

7579번: 앱

 

2. 메모이제이션과 결정문제

배낭문제의 변형, 값어치의 최대화가 아닌 비용이 최소인 값

 

이 문제는 아래와 같은 일반적인 방법으로 메모이제이션하는것은 불가능하다

 

(메모리의 최대 크기가 10,000,000, N의 크기가 100이기 때문에 128 MB보다 더 많은 메모리가 필요하다)

solve(i, mem) = mem만큼 메모리를 비웠을때, i번째 인덱스에서 시작하여 최소인 cost를 리턴  solve(i, mem) = min( solve(i+1, mem),                              solve(i+1, mem + m[i]) + c[i])

 

그러므로 아래와 같이 인덱스와 비용으로 값을 결정짓는 함수를 만들고, 그 변수들로 메모이제이션을 해야한다.

solve(i, cost) = i번째 인덱스에서 시작해서, cost이내의 비용을 지불할 수 있는 경우의 수 중                    최대 메모리 크기 리턴 solve(i, mem) = max(solve(i+1, cost),                             solve(i+1, cost - c[i]) + m[i] )

 

하지만 이 함수는 우리가 원하는 값을 반환해주지 않는다.

 

우리가 원하는 값은 변수로 들어가는 cost값이다.

 

따라서 모든 cost, 즉 0에서 MAX값까지 대입하여 

 

가장 처음으로 저 함수의 리턴값이 주어진 경계값 M보다 클경우의 cost값을 얻어내야한다.

 

 또한, 0~MAX의 범위의 값들을 전부 대입하지 않고, 이진 탐색을 이용하여 더 빠르게 값을 구할 수 있다.

(이 문제에서는 MAX값이 그리 크지 않으므로 속도향상이 미미하다)

 

이와 같이 최적화하는 문제는 탐색을 통해 값을 결정짓는 결정 문제로 변형 시킬 수 있다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <numeric>
using namespace std;
int N, M;
vector<int> C;
vector<int> A;
const int MAX = 10001;
 
int cache[101][MAX];
 
int solve(int idx, int cost) {
    if(idx == N) {
        return 0;
    }
    int& ret = cache[idx][cost];
    if(ret != -1) {
        return ret;
    }
    
    ret = solve(idx + 1, cost);
    if(C[idx] <= cost)
        ret = max(ret, solve(idx + 1, cost - C[idx]) + A[idx]);
    return ret;
}
 
int bsearch() {
    int lo = -1, hi = accumulate(C.begin(), C.end(), (int)0), mid;
    while(lo + 1 != hi) {
        mid = (lo+hi)/2;
        if(solve(0, mid) >= M) {
            hi = mid;
        }
        else {
            lo = mid;
        }
    }
    return hi;
}
 
int main() {
    cin>>N>>M;
    A = C = vector<int>(N);
    memset(cache, -1, sizeof cache);
    
    for(int i = 0; i < N; i++) {
        cin>>A[i];
    }
 
    for(int i = 0; i < N; i++) {
        cin>>C[i];
    }
    cout<<bsearch();
}