백준 7579번 : 앱

  뭔가 DP는 풀어도 풀어도 매번 어려운 느낌이다. 분명 풀이 방식은 거의 정해져 있고 대부분 비슷한데 왜 '아 쉽네~'하면서 풀리지를 않는지...

 

  이번 문제도 역시 정석적인 DP 풀이다. 다만 원래라면 i번째 앱까지 봤을 때 j만큼의 메모리를 확보했을 때 최소 cost를 저장하는 2차원 배열을 만들었어야 할 것 같지만 문제는 확보해야 할 메모리의 범위가 천만일 수도 있다는 점이다! 앱의 최대 개수가 100이니까 이대로 이차원 배열을 만들면 10억 크기의 배열을 만들어야 한다..! 이건 아니다... 싶어서 어떻게 할까 고민을 열심히 하다가 찾아낸 방법이 최대 코스트가 1만이라는 사실을 알았다. 앱의 최대 개수가 100이고 앱 하나의 최대 코스트가 100이니까 최악의 경우라도 코스트는 100 * 100을 넘지 않는다!

 

dp[i][j]

i번째 앱까지 살펴봤을 때 정확히 j의 코스트로 확보할 수 있는 최대 메모리

 

  이 정의는 다른 사람들의 풀이와 약간 다르다. 내가 참고한 블로그에는 dp[i][j]를 'i번째 앱까지 살펴봤을 때 j의 코스트로 확보할 수 있는 최대 메모리'라고 했었다. 굳이 정확히라는 표현을 쓰지 않아도 답은 제대로 나오지만 이 dp를 실제로 출력해봤을 때 정의에 맞지 않는 경우에 생기기 때문에 정확히라는 표현을 쓰고 싶었다.

 

문제에서 주어진 예제를 이용해 2차원 배열을 그려보면 위의 표와 같다.

 

  각 앱에 대해서 그 앱을 비활성하는 경우와 활성화된 채로 두는 경우가 있다. 그래서 이전 dp가 0이 아닌 지점에서 두 갈래로 길이 계속 나눠지게 된다. 그와 동시에 최댓값만을 dp에 저장해둠으로써 정의에 맞는 배열을 완성할 수 있다. 마지막으로 문제에서 요구하는 메모리만큼의 값 이상을 가지고 있는 열의 최솟값을 출력해주면 된다!

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int memory[102];
int cost[102];
int dp[102][10002];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++)
    {
        cin >> memory[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> cost[i];
    }
    
    int ans = 987654321;
    // dp[i][j] : i번째 앱까지 봤을 때 정확히 j 코스트를 소모해서 얻을 수 있는 최대 메모리
    dp[0][cost[0]] = memory[0];
    for(int i = 1; i < n; i++)
    {
        dp[i][cost[i]] = memory[i];
        for(int j = 0; j <= 10000; j++)
        {
            if(j-cost[i] >= 0 && dp[i-1][j-cost[i]] != 0) dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]] + memory[i]);
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            
            if(dp[i][j] >= m) ans = min(ans, j);
        }
    }
    
    cout << ans;
     
    return 0;
}