BOJ 7579 앱 / C++

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

7579번: 앱

백준 온라인저지 7579번 앱 문제입니다.

 

아이디어

메모리를 확보하기 위해 앱을 비활성화 시키는 촤소 비용을 찾기 위한 점화식을 찾는 것이 문제의 핵심이 됩니다.

knapsack 문제 유형인데요, 비용에 따른 최대 메모리를 찾아내면 됩니다.

#include<iostream>
#define MAX 100
#define COST_MAX 10004
using namespace std;

int appInfo[2][MAX];
int dp[COST_MAX];
int n, m;

int max(int a, int b) {
	return a > b ? a : b;
}

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		cin >> appInfo[1][i];
	
	
	for (int i = 0; i < n; i++) 
		cin >> appInfo[0][i];
	
	
}

void solution() {
	for (int i = 0; i < n; i++) {
		for (int j = COST_MAX - 1; j >= appInfo[0][i]; j--) {
			dp[j] = max(dp[j], dp[j - appInfo[0][i]] + appInfo[1][i]);
		}
	}
	for (int i = 0; i < COST_MAX; i++) {
		if (dp[i] >= m) {
			cout << i;
			return;
		}
	}

}
int main(void) {
	input();
	solution();
}