[C++] 백준 12865. 평범한 배낭

🌽 문제

🥕 입출력

🥔 풀이

가장 긴 증가하는 플라토닉 보봉 수열이 뭐 그런 문제를 풀어낸 뒤로
모든 DP 문제에 해당 코드를 대입해보는 습관이 생겼다
당연히 맨날 틀리는데 매번 좌절하는 나 웃긴다(안웃김)

하여간 이 문제는 또 다르게 접근해야 한다.
플라토닉 수열을 풀 때는
dp[i] = arr[i]를 포함할 때 얻을 수 있는 최대 가치로 뒀다면
배낭이 문제에서는
dp[w] = 무게 w를 담았을 때 얻을 수 있는 최대 가치로 잡는다.

첫 번째 방식처럼 잡게 되면 아래와 같은 문제가 발생한다고 한다.

주의: for문을 뒤에서부터 돌아야 각 아이템을 중복 사용하지 않을 수 있다.
나는 언제쯤 이런 코드를 스스로 생각해낼 수 있을가?

🥬 코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	vector<int> dp(k + 1, 0);
	for (int i = 0; i < n; i++) {
		int w, v;
		cin >> w >> v;
		for (int j = k; j >= w; j--) {
			dp[j] = max(dp[j], dp[j - w] + v);
		}
	}
	cout << dp[k];

	return 0;
}

🥜 채점

골드5는 쉽게 푸는 사람 하고 싶다