BOJ 7579 앱

 

 

문제 링크 : https://www.acmicpc.net/problem/7579

7579번: 앱

 

조건에서 메모리의 크기가 비용의 크기보다 훨씬 범위도 넓고 큰 값을 다룬다.

문제를 다르게 해석하는 것이 풀이를 용이하게 만들어 줄 듯하다.

일정량의 메모리를 확보하기 위한 최소 비용을 구하기 보다 일정 비용으로 확보할 수 있는 최대 메모리를 구해보자.

즉, dp[i][j] 를 i 번째 앱까지 j 비용으로 확보할 수 있는 최대 메모리로 두겠다는 의미이다.

 

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int N,M;
int mem[101], cst[101], dp[101][10001];

int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) scanf("%d",&mem[i]);
    for(int i=1;i<=N;i++) scanf("%d",&cst[i]);
    
    dp[1][cst[1]]=mem[1];
    for(int i=2;i<=N;i++){
        for(int j=0;j<=10000;j++){
            dp[i][j]=dp[i-1][j];
            if(cst[i]<=j)
                dp[i][j]=max(dp[i][j], dp[i-1][j-cst[i]]+mem[i]);
        }
    }
    
    for(int i=0;i<=10000;i++){
        if(dp[N][i]>=M){
            printf("%d\n",i); 
            break;
        }
    }
}

 

이중 for 문 내부에서 사용된

$$ dp[i][j]=dp[i-1][j] $$

는 dp[i][j] 의 하한을 설정하고 있다.

 

이미 i-1 번째 앱까지를 이용해서 j 비용으로 dp[i-1][j] 의 메모리를 확보할 수 있었다.

따라서 i 번째 앱을 추가해서 고려했을 때 최소 dp[i-1][j] 만큼의 메모리는 확보할 수 있다는 뜻이다.