[C++] 백준/BOJ - 7579 : 앱

---

문제 이해 단계

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

7579번: 앱

N개의 앱이 존재한다. N개의 앱에는 2가지 정보가 들어있는데,
(사용 중인 메모리의 바이트 수, 비활성화했을 때의 비용) 2가지이다.

M 바이트를 확보해야 하기 때문에, N개의 앱 중 몇 가지를 골라서 비활성화해야 한다.
이때 비활성화 했을 때의 비용을 최소화하여 M 바이트를 확보해야 한다.

최소 비용일 때를 출력하는 문제

 

---

문제 접근 단계

---

제한 사항 분석

앱의 개수(N)는 최대 100개까지 가능하다.

그리고 M 바이트를 확보해야 하는데, 여기서 M은 최대 10,000,000까지 가능하다.

비활성화했을 때의 비용(c)의 최대는 100까지 가능하다.

 

---

문제 유형 판단

M 바이트의 메모리를 확보해야 하는데, N개의 후보가 있다.
그리고 해당 원소를 사용하는 데는 비용이 든다.

이 말을 살짝만 다르게 하면, 굉장히 보편적인 문제가 된다.

N개의 보석이 있다. 보석은 (가치, 무게)의 정보로 이뤄져 있다.
가방에 보석을 담아 M 이상의 가치를 얻어야 할 때, 가방의 무게제한은 최소 몇 kg여야 하는가?

즉 해당 문제는 대표적인 DP에 배낭문제이다.

배낭 문제는 예전 포스팅에서 자세히 다룬 적이 있으니 링크를 달아두겠다.
https://howudong.tistory.com/106

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

 

---

일반적인 배낭 알고리즘과의 차이

일반적인 배낭 문제와 이 문제는 다른 점이 있다.

일반적인 배낭 문제에서는 얻을 수 있는 최대 이익을 구한다.
그런데 이 문제에서는 구해야 할 이익이 주어지고, 이 이익을 얻기 위해 필요한 최소 비용을 구하는 문제이다.

그런데 여기서는 문제가 있다.

일반적인 배낭 문제에서는 점화식을 세울 때, 
dp [i][j] = k : 최대 무게가 j인 가방에서 i까지 검사했을 때의 최대 이익이라는 뜻이다.

여기서는 최대 무게 j는 M을 말하는데, M이 최대 10,000,000까지이다.

배열로 여기까지 선언하면 메모리초과가 발생하기 때문에 다른 방법으로 접근해야 한다.

그래서 비용(c)의 최댓값이 100이고, N도 100이기 때문에
비용의 합은 최대 10,000까지 밖에 되지 않는다.

그걸 이용해서 점화식을 변형해서 다르게 세운다.

dp [i][j] = k : i번째 원소까지 총비용 j를 썼을 때, 최대 이익은 k이다.
라는 뜻으로 만든다.

이 이외에는 일반적인 배낭알고리즘과
비슷한 형식으로 점화식이 나온다.

if(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])
이렇게 된다.

이를 코드로 구현하면 된다.

 

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;



int dp[101][10001] = {0,};
int memory[101] = {0,};
int cost[101] = {0,};
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;

    int len = 0;
    for(int i = 1; i <= N; i++) cin >> memory[i];
    for(int i = 1; i <= N; i++) {
        cin >> cost[i];
        len += cost[i]; // 가능한 최대 무게
    }

    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= len; j++){
            
            // 점화식
            if(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]);
        }
    }

    // N번째까지 탐색했을 때 최초로 M이 나오는 것이 정답
    for(int i = 0; i <= len; i++){
        if(dp[N][i] >= M){
            cout << i;
            return 0;
        }
    }
}

코드는 굉장히 간단하다. 점화식만 적용시키면 된다.

en은 가능한 최대 길이까지만 반복시키면 된다.
그리고 정답은 최솟값을 구하는 것이기 때문에 무게가 0부터 시작하여 최초로 M을 넘을 때가 답이 된다.

 

 

---

시행착오

처음에는 그리디로 풀었는데, 배낭 알고리즘인지는 꿈에도 몰랐다.

말을 살짝만 틀었을 뿐인데도 깨닫지 못했다. 역시 어렵긴 어렵다.
DP 문제는 역시 많이 풀어보는 게 답인 것 같다.

생활비..

https://toss.me/howudong

howudong님에게 보내주세요