[백준] 12865 평범한 배낭

[백준] 12865 평범한 배낭

• https://www.acmicpc.net/problem/12865

틀린 풀이

• 7%에서 시간 초과

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

int N, K;
vector<int> W;
vector<int> V;

int answer = 0;

void solve(int curIdx, int curW, int curV) {
	if (curIdx == N) {
		answer = max(answer, curV);
		return;
	}

	//현재 인덱스의 물건 가방에 넣는 경우
	if ((curW + W[curIdx]) <= K) {
		solve(curIdx + 1, curW + W[curIdx], curV + V[curIdx]);
	}
	//현재 인덱스의 물건 가방에 넣지 않는 경우
	solve(curIdx + 1, curW, curV);

	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int w, v;
		cin >> w >> v;
		W.push_back(w);
		V.push_back(v);
	}

	solve(0, 0, 0);
	
	cout << answer;
	return 0;
}

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

int N, K;
vector<int> W;
vector<int> V;

int answer = 0;

int solve(int curIdx, int curW) {
	if (curIdx == N) {
		return 0;
	}

	int res = 0;

	//현재 인덱스의 물건 가방에 넣는 경우
	if ((curW + W[curIdx]) <= K) {
		res = max(res, V[curIdx] + solve(curIdx + 1, curW + W[curIdx]));
	}
	//현재 인덱스의 물건 가방에 넣지 않는 경우
	res = max(res, solve(curIdx + 1, curW));

	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int w, v;
		cin >> w >> v;
		W.push_back(w);
		V.push_back(v);
	}

	cout << solve(0, 0);

	return 0;
}

풀이

• 메모이제이션

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

int N, K;
vector<int> W;
vector<int> V;

int answer = 0;

int cache[100][100001];

int solve(int curIdx, int curW) {
	if (curIdx == N) {
		return 0;
	}

	int& res = cache[curIdx][curW];
	if (res != -1) return res;

	//현재 인덱스의 물건 가방에 넣는 경우
	if ((curW + W[curIdx]) <= K) {
		res = max(res, V[curIdx] + solve(curIdx + 1, curW + W[curIdx]));
	}
	//현재 인덱스의 물건 가방에 넣지 않는 경우
	res = max(res, solve(curIdx + 1, curW));

	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; ++i) {
		int w, v;
		cin >> w >> v;
		W.push_back(w);
		V.push_back(v);
	}

	//캐시 초기화
	for (int i = 0; i < 100; ++i) {
		for (int j = 0; j < 100001; ++j) {
			cache[i][j] = -1;
		}
	}
	cout << solve(0, 0);

	return 0;
}