급하게임개발

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

이 문제는 dp를 활용한 0-1 냅색 문제이다 즉 어떠한 원소를 사용할지 말지에 대해서 dp로 계속 값을 갱신해주는 것이다

예제를 표로 나면 이렇게 된다  

여기를 주목해보자 30과 10까지만 사용해서 5초를 만들었을의 최대무게는 40이였다 하지만 이제 20을 넣는다고 가정하자
여기서 5초로는 40밖에 이전에는 만들지 못했는데 20이 들어오게되면서 30과 10으로 만들었던 3초 더하기 현재 2초 5초를 만들면서 60이 된다

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

using namespace std;
int n, m;
int memory[101];
int cost[101];

// i번째 앱을 선택 했을 때의 비용 j dp[i][j]에는 이때의 최대 무게가 들어감
int dp[101][10001];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> memory[i];
	}
	int total = 0;
	for (int j = 1; j <= n; j++) {
		cin >> cost[j];
		total += cost[j];
	}
	int ans = 100001;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= total; j++) {
			// j가 현재 cost[i] 내가 넣으려는 cost보다 작으면 넣을 수 없으니 이전 값 사용
			if (j < cost[i])
				dp[i][j] = dp[i - 1][j];
			// 아닐 때느 나 이전까지만 넣은 애들 중에 현재 계산하려는 cost에서 나의 cost를 빼고 나의 무게를 더한거
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]);

			if (dp[i][j] >= m)
				ans = min(ans, j);
		}
	}
	
	cout << ans;
}

코드로는 이렇게 된다