[백준 7579] 앱

• 문제 : 7579 앱

• 유형 : DP

• 아이디어 : 배낭문제와 유사하지만 최대 메모리가 1e7이기 때문에 dp테이블을 메모리로 잡으면 풀 수가 없다. 그렇기 때문에 비용에 따라서 가질 수 있는 최대 메모리를 구해서 M보다 큰 경우중 비용이 가장 작은 것을 찾는 방식으로 풀어야 한다.

• 풀이 : dp 테이블은 i비용까지 사용했을 때 최대 메모리로 설정하였고 점화식은

	dp[i] = max(dp[i], dp[i-cost[j]] + memory[j])

바텀업 방식으로 진행하면 이전 인덱스의 변화가 다음 인덱스에 영향을 주기 때문에 탑다운으로 진행한다

그리고 최대 메모리값들 중 M을 넘는 것들 중 최소 비용을 구한다.

• 코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n, m;
pair<int, int > arr[101];
int dp[10001];



int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> arr[i].first;
	for (int i = 1; i <= n; i++) cin >> arr[i].second;


	for (int i = 1; i <= n; i++) {
		for (int j = 10000; j >= arr[i].second; j--) {
			dp[j] = max(dp[j], dp[j - arr[i].second] + arr[i].first);
		}
	}

	int ans = 0;
	int M = 1e9;
	for (int i = 0; i <= 10000; i++) {
		if (dp[i] >= m && M > dp[i]) {
			ans = i;
			M = dp[i];
		}
	}

	cout << ans;

	return 0;
}