백준/G3 7579-앱(c++) 풀이, 코드

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

난이도: G3

 

배낭문제의 일종으로 기계오리연구(https://www.acmicpc.net/problem/28082)와 유사한 문제이다.

dp[i]: i의 비용으로 확보할 수 있는 최대 메모리 용량이다. N과 비용이 0~100이므로 O(100*10000)의 시간복잡도로 풀 수 있다. dp[10001]을 모두 구한 후, 그중 M 이상을 값을 가지는 비용 중 최소가 답이다.

 

#include <iostream>
#include <vector>

using namespace std;

int dp[10001];
vector<int> a;
vector<int> m;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, M; cin >> N >> M;

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

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < N; j++) {
			int tmp; cin >> tmp;
			if (i == 0) a.push_back(tmp);
			else m.push_back(tmp);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 10000; j >= 0; j--) {
			if (j >= m[i]) dp[j] = max(dp[j], dp[j - m[i]] + a[i]);
		}
	}

	int ans = 1000000001;
	for (int i = 0; i <= 10000; i++) {
		if (M <= dp[i]) ans = min(ans, i);
	}

	cout << ans;

	return 0;
}

 

유사한 문제를 풀어봤는데도 dp, 배낭문제는 어렵다..