[BOJ] 7579. 앱 - c++

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

C++풀이

dp[i][c]= 앱 1~i까지만 고려하고 소요 비용이 c일때의 최대 메모리

-knapsack 문제에서 value배열=>memory배열, weight배열=>cost배열
-2차원 dp배열에서 가로축을 memory로 설정 시 1억 넘어감 -> 임시 비용의 총합(sum)값을 가로축으로 사용한다.

int memory[101];
int cost[101];
int dp[101][10001];//물건 1~i까지만 고려하고 소요 비용이 c일 때의 최대 메모리 
using namespace std;
int N,M;
int sum;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        cin>>memory[i];
    }
    for(int i=1;i<=N;i++){
        cin>>cost[i];
        sum+=cost[i];
    }
    
    
    for(int i=1;i<=N;i++){
        for(int c=0;c<=sum;c++){
            if(cost[i]>c) // 물건i를 비활성화 시키는 비용이 임시 비용의 용량을 초과하면
                dp[i][c]=(dp[i-1][c]);
            else//물건 i를 비활성화 시키는 경우와 시키지 않는 경우 고려 
                dp[i][c]=max(dp[i-1][c],dp[i-1][c-cost[i]]+memory[i]);
        }
    }
    for (int i = 0; i <= sum; i++)
	{
		if (dp[N][i] >= M)
		{
			cout << i << endl;
			break;
		}	
	}
}