[BOJ] 앱

[BOJ] 앱

Problem URL : 앱

[1] DFS를 이용한 풀이

#include <iostream>
#include <cstring>
#define INF 987654321

using namespace std;

int cost[101];
int memory[101];
int dp[101][10001];
int N, M;

int dfs(int idx, int costSum) {
	if (idx >= N) return 0;
	int& ret = dp[idx][costSum];
	if (ret != -1) return ret;
	ret = dfs(idx + 1, costSum);
	if (cost[idx] <= costSum) {
		ret = max(ret, memory[idx] + dfs(idx + 1, costSum - cost[idx]));
	}
	return ret;
}


int main() {
	memset(dp, -1, sizeof(dp));
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> memory[i];
	for (int i = 0; i < N; i++) cin >> cost[i];

	int costSum = 0;
	while (1) {
		if (dfs(0, costSum) >= M) {
			break;
		}
		costSum++;
	}
	cout << costSum << "\n";
	return 0;
}

[2] DP를 이용한 풀이

#include <iostream>
#include <cstring>
#include <algorithm>
#define INF 987654321

using namespace std;

int cost[101];
int memory[101];
int dp[101][10001];
int N, M;

int main() {
	memset(dp, -1, sizeof(dp));
	cin >> N >> M;
	int costSum = 0;
	for (int i = 0; i < N; i++) cin >> memory[i];
	for (int i = 0; i < N; i++) {
		cin >> cost[i];
		costSum += cost[i];
	}

	memset(dp, 0, sizeof(dp));

	for (int i = cost[0]; i <= costSum; i++) {
		dp[0][i] = memory[0];
	}
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < cost[i]; j++) {
			dp[i][j] = dp[i - 1][j];
		}
		for (int j = cost[i]; j <= costSum; j++) {
			dp[i][j] = max(dp[i - 1][j],dp[i-1][j-cost[i]] + memory[i]);
		}
	}
	for (int i = 0; ; i++) {
		if (dp[N - 1][i] >= M) {
			cout << i;
			break;
		}
	}
	
	return 0;
}