(7579) 앱

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

단계별로 풀어보기

31단계(동적 계획법 2) 6번째

 

 

 

또다른 냅색 문제. dp[b]를 (a번째 앱까지 탐색해) b바이트를 절약했을 때 최소 비용으로 두고 풀면... 메모리 바이트의 범위가 이상하다. b의 최대값은 천만이나 되기 때문에 dp[a][b]는 커녕 dp[b]로 선언해도 메모리가 터진다.

메모리에 비해 비용의 범위가 매우 작으므로, 메모리 대신 비용을 dp로 사용해야 한다.

dp[c]를 (a번째 앱까지 탐색해) 비용 c를 절약했을 때 확보 가능한 메모리 최댓값으로 두고 DP를 돌리면 된다.

dp[c]의 값이 M 이상이 되는 c의 최소값이 우리가 원하는 답이다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  int N= n*100;
  
  vector<pair<int,int>> v(n);
  vector<int> dp(N+1, -1);
  
  for(int i=0;i<n;i++)  cin >> v[i].first;
  for(int i=0;i<n;i++)  cin >> v[i].second;
  
  dp[0]= 0;
  
  for(int i=0;i<n;i++){
    for(int j=N;j>=0;j--){
      if(dp[j]==-1)  continue;
      
      if(j+v[i].second<=N)  dp[j+v[i].second]= max(dp[j+v[i].second], dp[j]+v[i].first);
    }
  }
  
  for(int i=0;i<=N;i++){
    if(dp[i]>=m){
      cout << i;
      
      break;
    }
  }
  
  return 0;
}