[백준] 7579번 앱

7579번: 앱

처음엔 1부터 M까지 메모리를 기준으로 비용을 구하려 했는데

시간 초과가 눈에 뻔해서 다른 방법으로 바꾸었다.

 

0부터 최댓값(모든 비용을 다 더한 값)까지 비용을 기준으로 

배낭 채우기 방식을 이용하여 최대 메모리를 dp배열에 채워 넣는다.

 

최종 배열에서 가장 먼저 M이상인 값이 나온 인덱스를 출력하면

그게 바로 최소 비용이다.

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, cnt, mem[101], cost[101], dp[2][10001];
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> mem[i];
	for (int i = 0; i < N; i++) cin >> cost[i], cnt += cost[i];

	for (int i = cost[0]; i <= cnt; i++) dp[0][i] = mem[0]; // 첫 줄
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < cost[i]; j++) dp[i % 2][j] = dp[1 - i % 2][j]; // 해당 비용 전까지는 이전 dp 가져옴
		for (int j = cost[i]; j <= cnt; j++) dp[i % 2][j] = max(dp[1 - i % 2][j], dp[1 - i % 2][j - cost[i]] + mem[i]); // 해당 비용부터는 계산한 값 넣음
	}

	for (int i = 0; i <= cnt; i++) { // 최종 결과에서 메모리를 먼저 M 이상 가지는 비용이 최소 비용임
		if (dp[(N - 1) % 2][i] >= M) {
			cout << i;
			break;
		}
	}
	return 0;
}