[백준] 7579번 : 앱 c++ (DP)

솔직히 DP는 매번 접근법을 잘 모르겠다...

대충 느낌은 DP 일거라 생각이 들지만 어떻게 해야할 지는 상세히는 모르겠다.

(열심히 공부하자..ㅠㅠ)

 

접근:

이전 결과를 이용하여 현재 결과를 결정하는 방식으로 풀 수 있기 때문에 DP로 풀면된다.

 

전략:

이전 정보를 저장하는 dp[101][10000] 배열을 만들고,  매 앱을 하나씩 확인하면서, 이전 상태를 참고하여 앱의 cost를 선택하거나 선택하지 않았을때의 최대 확보 할 수 있는 메모리를 비교한다. 끝에는 모든 앱을 비교한 상태들 중  cost가 가장 작은 것을 선택한다.

 

코드:

#include <iostream>
#include <vector>
using namespace std;
int n,m;
struct App{
    int mem;
    int cost;
    
};

vector<App> app;
int dp[101][10001]; // n , c

void print(){
    for(int i=0;i <n ;i++){
        cout << app[i].mem << ' '<< app[i].cost << '\n';
    }
}

int main(){
    cin >> n >> m;
    app.resize(n+1);

    for(int i=1;i<=n;i++){
        cin >> app[i].mem;
    }
    for(int i=1;i<=n;i++){
        cin >> app[i].cost;
    }
    int res = 1000000000;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=10000;j++){
            if(j - app[i].cost >= 0 ){
                dp[i][j] = max(dp[i][j], dp[i-1][j-app[i].cost] + app[i].mem); 
            }
            
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            
            if(dp[i][j] >= m) res = min(res , j);
        }
        
    }
    // print();
    cout << res << '\n';

    return 0;
}