백준 7579 앱

알고리즘 스터디에서 친구가 가져왔던 문제이다. 0-1 Knapsack문제 유형을 보고 잡은 문제라는데, 좀 어려웠다.

그냥 0-1 knapsack 문제로 생각하면, 배낭크기를 메모리로 따져서 col에 M개 열을 만들어 해볼까 했는데 메모리의 최대값이 10000000이라 배열으로 선언을 할 수 없을 것 같다.

 

그럼 어떻게 할까...? 친구가 풀다가 솔루션을 확인했는데, 그 방식이 너무 신기했다. col을 다른 값을 사용해서 채우는 방법이 있더라. 이 문제 같은 경우에는, col에 cost를 넣어둬 문제를 해결했다.

따라서 dp[i][j] = i번째 앱까지 봤을때, j비용으로 얻을 수 있는 메모리의 크기가 된다.

dp 배열의 내용을 한번 보자,

	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]
dp[1]	0	0	0	30	30	30	30	30	30
dp[2]	10	10	10	40	40	40	40	40	40
dp[3]	10	10	10	40	40	40	60	60	60
dp[4]	10	10	10	40	40	45	60	60	75
dp[5]	10	10	10	40	50	50	60	80	80

배열을 채울 때, 만약 i 번째 앱의 비용이 j 보다 적게 되면(해당 앱을 삭제할 수 없으므로) 그냥 바로 위 값을 가져온다(dp[i][j] = dp[i-1][j])

만약 i번째 앱의 비용이 j와 같거나 크면(해당 앱을 삭제하는 선택을 할 수 있으므로) 바로 위 값과, 그 앱을 삭제했을 때 메모리 양 중 큰 값을 가져온다(std::max(dp[i-1][j], dp[i-1][j-apps[i].cost] + apps[i].mem))

이렇게 순회하며 dp 값을 구하고 나서, 마지막 행에서 우리가 원하는 메모리 양을 넘는 순간의 cost를 구하면, 해당 양의 메모리를 구하는데 필요한 최소 비용을 구할 수 있다.

---

#include <iostream>
#include <vector>
class app{
public:
    int cost;
    int memory;

    app(int memory)
    {
        this->memory = memory;
    }
};
int main()
{
    int N, M;
    std::cin >> N >> M;
    std::vector<app> apps;
    apps.push_back(app(-1));
    for (int i = 1; i <= N; i++)
    {
        int mem_tmp;
        std::cin >> mem_tmp;
        app temp(mem_tmp);
        apps.push_back(temp);
    }
    int costSum = 0;
    for (int i = 1; i <= N; i++)
    {
        int cost_tmp;
        std::cin >> cost_tmp;
        apps[i].cost = cost_tmp;
        costSum += cost_tmp;
    }
    // long dp[N+1][costSum+1];
    std::vector<std::vector<long> > dp(N + 1, std::vector<long>(costSum + 1, 0));
    // memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= N; i++)
    {
        for (int costLimit = 0; costLimit <= costSum; costLimit++)
        {
            if (costLimit < apps[i].cost) // 현재 앱 죽여도 costLimit 만족 안될때.
                dp[i][costLimit] = dp[i - 1][costLimit]; // 그냥 위 칸 당겨오기
            else
                dp[i][costLimit] = std::max(dp[i - 1][costLimit], dp[i - 1][costLimit - apps[i].cost] + apps[i].memory);
        }
    }
    long mincost;
    for (mincost = 0; mincost <= costSum; mincost++)
    {
        if(dp[N][mincost] >= M)
            break;
    }
    std::cout << mincost;

}

/*
Knapsack 문제와 유사하지만, 어떤 것을 축으로 삼아 제한 조건을 줄 지 선정하는것이 중요하다.
여기서는 dp[i][j] 를, j cost 안에서 i 번째 아이템까지 사용해 확보 가능한 최대 메모리 양으로 정한다.
knapsack 에서는 무게를 하나씩 늘려가며 i번째 아이템까지 사용해 무게 j 배낭에 담을 수 있는 가치였다.
dp를 이렇게 정의해두고, 우리는 어떻게 이 dp를 채워가느냐?
만약, i번째 아이템이 현재 j 보다 비용이 크면, 우리는 이 앱을 삭제할 수 없다. 따라서 그냥 바로 위 (dp[i-1][j])를 가져온다.
만약, i번째 아이템이 현재 j 보다 비용이 작거나 같으면, 우리는 이 앱을 삭제할 수 있다. 삭제 안하는경우(dp[i-1][j])와 삭제 하는 경우(dp[i-1][j - apps[i].cost] + apps[i].memory) 중 최대값을 가져다 dp에 넣는다.

이렇게 완성된 dp 배열은, 마지막 줄을 탐색하며, 우리가 원하는 메모리 양이 넘는 순간의 인덱스(cost)값을 구하면 된다.
바로 그 값이, 그 cost를 최소화 하면서 우리가 원하는 메모리를 확보한 상황이다/
*/

스터디할때 한번 봤었고, 다시 보면서 읽어도 진짜 이걸 문제만 보고 어떻게 솔루션을 내나 싶다. 어떻게 이렇게 문제를 푸는지 신기한 사람들이 많은 것 같다.

요즘 DP를 보는데, 이쪽 영역은 약간 수학의 영역인 느낌이다... 문제를 점화식을 세우는게 가장 중요한데, 그 가장 중요한게 제일 어려운 것 같다.

 

오늘도 평온한 하루 되길. 슨민.