백준 7579번 앱 (C++)

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

7579번: 앱

 

문제를 보면 어떻게 접근해야할지 어려울 수 있다. 나도 처음에 dp라는 알고리즘 분류를 못봤다면 매우 어렵게 풀었을 것이다. 이 문제를 배낭 문제라고 판단해야할 프로세스는 다음과 같다.

 

1. 모든 경우의 수를 따져봐야한다. 그렇다면 경우의 수를 따질 수 있는 알고리즘을 검토한다.

2. 재귀, dfs 백트래킹, 브루트포스, dp

- 재귀: N이 100이므로 사용할 수 없다.

- dfs 백트래킹: 마찬가지로 시간초과가 날 가능성이 크다.

- 브루트포스: 구현이 어렵고 시간초과의 가능성이 크다.

 

3. 그렇다면 dp 중에서 어떤 dp인가? 1차원? 2차원?

4. 문제를 잘 보면 확보해야할 메모리가 정해져있고 그에 따른 패널티가 주어진다. 그러므로 이 것은 배낭문제임을 파악할 수 있다. 

 

배낭문제라고 생각이 들면 뭐가 weight이고 뭐가 value인지 판단이 필요하다. 여기서 목적은 M 바이트를 확보하는 것이다. 그러므로

 

dp[i][j] = i번째 앱까지 살펴봤을 때, 비활성화 비용이 j일 때 확보할 수 있는 가장 큰 메모리

 

가 된다. 그러므로 테이블을 채워나가다가 M과 같거나 큰 메모리가 확보되면 정답을 갱신하는 방식으로 사용하면 된다. 즉 행은 N 열은 비용의최대치가 된다. 여기서 비용은 100까지 들어올 수 있고 앱의 수가 100이므로 최대 비용은 100 * 100이 된다. 그래서 필요한 dp 배열의 크기는 100 x 10000 이다.

 

#include <iostream>
#include <vector>

using namespace std;

int dp[101][10001] = { 0, };

vector<pair<int, int>> app;

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int mem;
		cin >> mem;
		app.push_back({ mem, 0 });
	}

	for (int i = 0; i < N; i++) {
		int cost;
		cin >> cost;
		app[i].second = cost;
	}
	long long answer = 10001;
	for (int i = 1; i <= N; i++) {
		int weight = app[i - 1].second;
		int value = app[i - 1].first;
		for (int j = 0; j < 10001; j++) {
			if (j >= weight) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}

			if (dp[i][j] >= M) { answer = min(answer, (long long)j);}
		}
	}
	cout << answer << '\n';
}