[백준]7579 앱 #dp#배낭

배낭문제와 유사한 dp문제.

배낭	​	앱
가치	==	메모리
무게	==	비용

 

1. 풀이

(1) dp[i][j] : i번째 앱까지 끌 수있고, j 비용까지 가능할 때, 최대 메모리

(2) 비용이 0인 앱도 있으므로 0열은 0으로 채우지 않도록 주의.

(3) 최대 메모리를 찾는 문제이기 때문에 나올 수 있는 최대 비용까지 열을 확보해야한다.

(4) 점화식

dp[i][j]는 두가지 값을 비교하여 큰값을 넣는다.

  1) i-1번째 앱까지 끌 수 있는 상황.

    => dp[i-1][j]

  2) i-1번째 앱까지 끌 수 있는 상황에서 i번째 비용만큼이 확보된 값에서 i번째 앱을 끄는상황.

    => dp[i-1][j-(i의 비용)]+(i의 메모리)

5. 특정메모리(M)이상의 값을 확보할 수 있을 때 최소 비용을 찾으므로 탐색하면서 dp[i][j]의 값이 m이상인 값중 j값이 가장 작은값 찾는다.

​

2. 예시

​	1	2	3	4	5
메모리	30	10	20	35	40
비용	3	0	3	5	4

 

비용 앱	0	1	2	3	4	...
0	0	0	0	0	0
1	0	0	0	30	30
2	10	10	10	40	40
3	10	10	10	40	40

 

3. 소스코드

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

#define maxCost 10001
using namespace std;


// dp[i][c] : i번째 앱까지 넣을 수 있고, c비용까지 쓸 수 있을 때 최대 메모리
int dp[101][maxCost];

// m[i] : i번째 앱의 메모리
int m[101];

// c[i] : i번째 앱의 cost
int c[101];

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> m[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> c[i];
	}

	int ans = maxCost;
	for (int item = 1; item <= N; item++) {
		for (int cost = 0; cost < maxCost; cost++) {
			// item넣을 수 있을 때
			if (cost >= c[item]) {
				// item-1 까지 넣을 수 있는 상태에서 비교
				dp[item][cost] = max(dp[item - 1][cost], dp[item - 1][cost - c[item]]+m[item]);
			}
			else {
				dp[item][cost] = dp[item - 1][cost];
			}
			if (dp[item][cost] >= M and cost<ans) {
				ans = cost;
			}
		}
	}
	/*
	//출력확인
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < 80; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/

	cout << ans;

	return 0;
}