(C++) - 백준(BOJ) 7579번 : 앱 답

www.acmicpc.net/problem/7579

7579번: 앱

top down dp로 푼 문제였습니다.

 

풀이방법

 1. 두 가지의 상태로 나누어집니다.

     1-1. 현재 앱을 놔두는 경우에는 현재 남는 메모리는 그대로입니다.

 

     1-2. 비활성화하는 경우. 현재 남는 메모리 = 현재 남는 메모리 - 현재 앱을 다시 실행할 경우의 cost입니다.

 

 2. dp 점화식을 세웁니다.

    d 배열을 선언합니다. i번째 어플의 남은메모리 j로 확보할 수 있는 메모리양으로 정의될 수 있습니다.

    i번째 앱에 대해 확보되는 메모리양은 1번의 두 가지경우로 남은 메모리를 비교했을 때 최대값을 가져갑니다.

 

 

Code

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

int appNum, needMem;
int mem[101], cost[101], d[101][10001];

int dp(int cur, int memLeft){
    if(cur == appNum) return 0;
    int &ret = d[cur][memLeft];
    if(ret!=-1) return ret;
    ret = dp(cur+1,memLeft);
    if(memLeft >= cost[cur]) ret = max(ret,mem[cur] + dp(cur+1,memLeft - cost[cur]));
    return ret;
}

int main(){
    cin >> appNum >> needMem;
    for(int i = 0; i < appNum; i++) cin >> mem[i];
    for(int i = 0; i < appNum; i++) cin >> cost[i];
    memset(d,-1,sizeof(d));
    int memory = 0;
    while(1){
        if(dp(0,memory)>=needMem) {
            cout << memory;
            break;
        }
        memory++;
    }
}