BOJ-7579-앱

[changicho]

7579. 앱

링크

난이도	정답률(_%)
Gold III	37.075

설계

동적계획법

dp[i][j] : i번째 앱까지 메모리를 확보하는데 필요로 하는 비용

위와 같이 했을 때는, 메모리 초과가 발생한다. 앱의 개수가 아닌 cost를 index로 dp를 구성한다.

정리

내 코드 (ms)	빠른 코드 (ms)
0

고생한 점

코드

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

using namespace std;

struct app {
	int cost, memory;
};

vector<app> apps;
int dp[100001] = { 0, };

void solution() { 
	int N, M;

	cin >> N >> M;

	apps.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> apps[i].memory;
	}
	int max_cost = 0;
	for (int i = 0; i < N; i++) {
		cin >> apps[i].cost;
		max_cost += apps[i].cost;
	}

	// 각 앱을 순차적으로 돌아보면서 dp를 갱신한다.
	for (int i = 0; i < N; i++) {
		// 이전에 갱신한 값 vs 현재 cost에서 현재 앱을 중지시켰을 경우의 값
		// 값은 memory 총량을 의미
		for (int j = max_cost; j >= apps[i].cost; j--) {
			dp[j] = max(dp[j], dp[j - apps[i].cost] + apps[i].memory);
		}
	}

	// cost를 증가시키면서
	// dp[cost]에서 확보할 수 있는 memory양을 검사한다
	// 확보할 수 있는 memory >= M이 되면 그때의 cost가 답이다.
	int answer = 0;
	while (true) {
		if (answer > 10000 || dp[answer] >= M) break;
		
		answer++;
	}
	cout << answer << "\n"; 
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}