[BOJ] 7579 : 앱 - travelbeeee

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

---

[ 알고리즘풀이 ]

memory[N] := N번 째 앱의 메모리

cost[N] := N번 째 앱의 비용

 

1) 메모리를 기준으로 한 1차원 DP 정의.

dp[M] := 메모리 M을 사용했을 때, 최소 비용

→ dp[M] = min ( dp[M], dp[M - memory[i]] + cost[i] );

dp 배열을 채우는데 N개의 물건을 하나씩 추가해가며 dp배열을 탐색해야하므로 O(N * sum of Memory)의 시간 복잡도를 가진다. 최악의 경우 100 * 10,000,000 으로 아마 백준 테스트케이스 중에 하드한게 없어서 시간초과 문제에 걸리지 않은 것 같다.

#include<iostream>
#include<algorithm>
#define INF 99999999
using namespace std;

int N, M, memory[100] = {}, cost[100] = {}, s = 0;
int dp[10000001];

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

	cin >> N >> M;
	for (int i = 0; i < N; i++){
		cin >> memory[i];
		s += memory[i];
	}

	for (int i = 0; i < N; i++)
		cin >> cost[i];

	for (int i = 0; i <= s; i++)
		dp[i] = INF;

	dp[0] = 0, dp[memory[0]] = cost[0];

	for (int i = 1; i < N; i++) {
		for(int j = s; j >= memory[i]; j--)
			dp[j] = min(dp[j], dp[j - memory[i]] + cost[i]);
	}

	int ans = dp[M];
	for (int j = M; j <= s; j++)
		ans = min(ans, dp[j]);

	cout << ans;
}

 

2) 물건과 코스트를 기준으로 한 2차원 DP 정의.

dp[N][K] := 1 ~ N 번까지 물건을 사용해 코스트가 K일 때 최대 메모리.

→ dp[N][K] := max( dp[N - 1][K] , dp[N - 1][K - cost[i]] + memory[i] );

dp 배열을 채우는데 N개의 물건을 하나씩 추가해가며 dp배열을 탐색해야하므로 O(N * sum of Cost)의 시간 복잡도를 가진다. 따라서, 위의 1) 알고리즘보다 훨씬 좋은 시간 복잡도를 가진다.

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int N, M, memory[100] = {}, cost[100] = {}, s;
int dp[100][10001];

int main(void) {
	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];
		s += cost[i];
	}

	memset(dp, 0, sizeof(dp));


	dp[0][cost[0]] = memory[0];
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= s; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j - cost[i] >= 0)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + memory[i]);
		}
	}
	for (int j = 0; ; j++) {
		if (dp[N - 1][j] >= M) {
			cout << j;
			break;
		}
	}
	return 0;
}

---