[c/c++] 백준 7579

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

7579번: 앱

 

접근 방식

냅색(knapsack) 알고리즘을 이용하여 접근했다. 일반적인 알고리즘에서의 w(무게)를 메모리, v(가치)를 비용으로 대응했다. 하지만 이렇게 냅색 알고리즘을 이용하게 되면 배열의 크기가 100*10,000,000이 훨씬 넘어가게 되므로 제한 조건을 어기게 된다.

 

풀이 방법

배열의 크기가 문제가 되므로 배열의 크기를 줄일 방법을 생각했다. 위에서 생각했던 방법은 dp[i][j] : i번째까지 앱을 살펴봤을 때, 메모리가 j일 때 가치의 최댓값인데, 반대로 j를 가치로 하고 배열에 메모리를 저장하게 된다면 배열의 크기가 크다는 문제를 해결할 수 있다. 그래서 dp[i][j] : i번째까지 앱을 살펴봤을 때, 가치가 j이하를 만족하는 메모리 합의 최댓값이라고 정의했다.

코드

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    int cost_sum=0; //cost들의 총합
    int min_cost=987654321;
    int memory[101]={0};
    int cost[101]={0};
    int dp[101][10001]={0}; //dp[i][j] : i번째까지 앱을 살펴봤을 때, 가치가 j이하를 만족하는 메모리 합의 최댓값
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>memory[i];
    for(int i=1;i<=n;i++){
        cin>>cost[i];
        cost_sum+=cost[i];
    }
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=cost_sum;j++){
            if(j-cost[i]>=0){
                dp[i][j]=max(dp[i][j],dp[i-1][j-cost[i]]+memory[i]);
            }
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            if(dp[i][j]>=m){
                if(min_cost>j) min_cost=j;
            }
        }
    }
    cout<<min_cost;
    return 0;
}

dp를 다 구하고 값이 m이상인 값들 중에서 j가 최소인 값을 찾으면 된다.