[DP] BOJ 7579 앱 (C++)

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

7579번: 앱

 

문제 해결 알고리즘

 

dp[i][j]에서 i는 배열의 i번째 원소 까지라는 뜻이고 j는 시간이다. 

dp[i][j]는 i번째까지의 원소들 중에서 j시간을 썼을 때, 최대 메모리이다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N, M;

int Byte[101], Time[101], dp[101][10001], Sum = 0;

int main(){

    cin >> N >> M;

    for(int i=1;i<=N;i++) cin >> Byte[i];
    for(int i=1;i<=N;i++){
        cin >> Time[i];
        Sum += Time[i];
    } 

    for(int i=1;i<=N;i++){
        for(int j=0;j<=Sum;j++){

            if(j - Time[i] >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-Time[i]] + Byte[i]);
            dp[i][j] = max (dp[i][j], dp[i-1][j]);

        }
    }
	
    
  for (int i=0;i<=Sum;i++){
	if (dp[N][i] >= M){
		cout << i;
    		break;
	}	
  }
    


}