[백준] 7579-앱(C++), 배낭 문제 알고리즘

문제링크:www.acmicpc.net/problem/7579

7579번: 앱

 

배낭문제 알고리즘으로 해결하는 문제입니다.

 

근데 기존 배낭문제에서는 배낭에 넣을 수 있는 최대값을 구하잖아요?

근데 이문제는 최소 값을 구해야 하고 무게가 아닌 시간값을 구해야하는게 다른 문제입니다. 

그래서 시간과 무게를 반대로 생각해서 점화식을 구현하는 문제입니다.

 

이 문제가 어려우시다면 아래 문제를 먼저 풀어보세요.

 

gusdnr69.tistory.com/153 

[백준] 12865-평범한 배낭(C++), 배낭 문제 알고리즘

 

m[] 메모리 배열

c[]  비용 배열

 

dp[i][j]  i는 n개의 앱 중에서 몇번째 앱까지인지   j는 시간을 의미합니다.

이때 dp에 저장되는 값은 메모리값이 저장됩니다.

 

점화식은

if(j >= c[i])  dp[i][j] = max(dp[i-1][j], dp[i -1][j- c[i]] +m[i])

else dp[i][j] = dp[i-1][j] 

입니다.

 

dp[i][j] >= M 일때  min(result,j)를 통해서 결과값을 도출합니다.

 

 

아래는 정답코드입니다.

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

int N, M;
int m[101] = { 0, };
int c[101] = { 0, };
int dp[101][10001] = { 0, };
int result = 1000000000;


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;

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

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 10000; j++) {
			if (c[i] <= j)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + m[i]);
			else
				dp[i][j] = dp[i - 1][j];

			if (dp[i][j] >= M) result = min(result, j);
		}
	}
	

	cout << result << endl;

	return 0;
}