[백준/BOJ] 백준 7579번 : 앱

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

7579번: 앱

 

배낭 문제와 비슷하게 생각하여, cache[확인하는 앱의 인덱스][확인하는 인덱스의 앱까지 사용된 비용]에 "현재 앱까지 확인하고, 사용된 비용에서 확보할 수 있는 최대 메모리"를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>
using namespace std;

int n, m;
vector<int> ms(105, 0);
vector<int> cs(105, 0);
int cache[105][10005]; //[확인하는 앱의 인덱스][확인하는 인덱스의 앱까지 사용된 비용] = 현재 앱까지 확인하고, 사용된 비용에서 확보할 수 있는 최대 메모리
int result = numeric_limits<int>::max();

//배낭 문제와 비슷한 풀이로 생각

void pre() {
	for (int i = 0; i < 105; i++) {
		for (int j = 0; j < 10005; j++) {
			cache[i][j] = 0;
		}
	}
}

int main()
{
	pre();

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int input;
		cin >> input;

		ms[i] = input;
	}

	for (int i = 1; i <= n; i++) {
		int input;
		cin >> input;

		cs[i] = input;
	}

	for (int i = 1; i <= n; i++) {

		for (int j = 0; j < 10005; j++) {

			//현재 인덱스의 앱을 비활성화 해서 j 비용이 되는 경우
			if (j - cs[i] >= 0) {
				cache[i][j] = max(cache[i][j], cache[i - 1][j - cs[i]] + ms[i]);
			}

			//현재 인덱스의 앱을 비활성화 하지 않는 경우
			cache[i][j] = max(cache[i][j], cache[i - 1][j]);

			//m 메모리 이상 확보했을때
			if (cache[i][j] >= m) {
				result = min(result, j);
			}
		}
	}

	cout << result;

	return 0;
}