[BOJ/C++] 7579(앱)

1. Link

https://www.acmicpc.net/problem/7579
비슷한 문제(평범한 배낭): https://www.acmicpc.net/problem/12865

2. 풀이 과정

1. N개 중 몇 개를 비활성화 하여 M바이트 이상을 확보하라 -> KnapSack problem(DP)

• 대학교 전공이 컴퓨터 계열이라면 아마 한 번쯤은 들어봤을 knapsack 문제입니다. 다만 저는 들은 지 오래돼서 우격다짐으로 코드를 작성했네요 ㅎ헣..

• 암튼 간단하게 이야기하자면 우선 dp배열을 만든 근거는 row에서 N개의 앱을 파악하기 위해 100으로, column에서 N(<=100)개의 앱에 대한 cost(<=100)를 판단하기 위해 10000으로 설정했습니다.

• 이중 for문을 사용해 N개의 앱의 활성화, 비활성화 여부를 따집니다. 해당 칸이 받을 수 있는 값은 바로 위 칸의 값(활성화된 상태로 넘어감) 또는 위 행에서 cost만큼을 추가한 값(비활성화로 cost 사용) 중 하나이며, 그 중 최대값을 선택합니다.

• 마지막으로 N번째 dp배열을 0부터 돌면서 최소 cost에서 M 이상의 바이트를 절약하는 상황이 확인되면 해당 값을 출력하고 함수를 종료합니다.

3. 정답 코드

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

int n, m, finish;
int a[101], c[101];
int dp[101][10001];

void input() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
		finish += c[i];
	}
}

void solution() {
	input();
	dp[1][0] = 0;
	dp[1][c[1]] = a[1];
	for (int i = 2; i <= n; ++i) {
		for (int j = 0; j <= finish; ++j) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			dp[i][j + c[i]] = max(dp[i - 1][j] + a[i], dp[i - 1][j + c[i]]);
		}
	}

	for (int i = 0; i <= finish; ++i) {
		if (dp[n][i] >= m) {
			cout << i;
			return;
		}
	}
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}