[boj] 백준 7579 앱 (c++) - dp

[문제]

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

7579번: 앱

 

[풀이]

dp 문제.

이 문제를 푸는데 헤매었던 부분이 2가지 있었다. 

먼저 처음 dp 배열을 메모리 기준으로 만들어서 풀려고 했다. dp[i] = i 바이트의 메모리를 확보하기 위해 필요한 최소 비용으로 둔 후 dp[m] 에 해당하는 값을 출력하고자 했다. 예제는 잘 나왔으나 간과했던 부분은 딱 m 바이트가 아니라 m 바이트 이상의 메모리를 확보하는 경우가 더 최소의 비용이 될 수 있다는 것이다. 그러려면 m 바이트~10000000 까지의 범위에 대해 최소 비용을 찾아야 하는데 효율적이지 않은 방법이라 여겨져 dp 배열을 비용을 기준으로 바꿨다.

이제 dp[i] = i 비용으로 확보 가능한 최대한의 메모리 크기를 저장한다. 그럼 dp[i] 가 m과 같거나 커지는 순간의 i 값이 최소의 비용이 된다. cost를 기준으로 하면 dp 메모리도 더 효율적으로 사용 가능하다.

또 한가지 고려해야 할 점은 dp 점화식에서 j 값이 내림차순으로 계산되게 해야 한다는 것. n는 최대 100, cost 도 최대 100이므로 100*100부터 시작해서 j 값을 감소시켜야 한다. 만약 오름차순으로 계산하게 되면 이전에 계산된 dp[j] 값이 후에 반복문이 돌면서 다시 쓰이게 되는 일이 발생한다. 그렇게 되면 memory[i]가 추가로 더해지기 때문에 올바른 값을 구할 수 없음에 주의해야 한다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n, m;
int memory[101];
int cost[101];
int dp[10001]; //해당 비활성화 비용으로 확보 가능한 최대 메모리값

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> memory[i]; //바이트 수 저장
    }
    for(int i=0; i<n; i++){
        cin >> cost[i]; //비활성화할 경우의 비용
    }

    for(int i=0; i<n; i++){
        for(int j=100*100; j>=cost[i]; j--){
            dp[j] = max(dp[j], dp[j-cost[i]]+memory[i]);
        }
    }

    for(int i=0; i<100*100+1; i++){
        if(dp[i]>=m){
            cout << i;
            break;
        }
    }

}