문제
N개의 물건(무게 W, 가치 V)이 있을 때, 최대 무게 K 이내에서 가치의 합을 최대화하는 문제다. 각 물건은 한 번만 사용 가능하다.
핵심 아이디어
dp[i][j]= i번째 물건까지 고려했을 때, 무게 j 이내의 최대 가치.- 각 물건에 대해 넣는 경우와 넣지 않는 경우 중 최댓값을 선택한다.
- 점화식:
dp[i][j] = max(dp[i-1][j], v + dp[i-1][j-w])(j >= w일 때)
풀이
#include <iostream>
using namespace std;
int dp[101][100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int w, v;
cin >> w >> v;
for (int j = 1; j <= k; j++) {
if (j - w >= 0) {
dp[i][j] = max(dp[i - 1][j], v + dp[i - 1][j - w]);
} else {
dp[i][j] = dp[i][w - 1];
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
cout << dp[n][k] << '\n';
return 0;
}
주요 포인트
dp[i-1][j-w]는 현재 물건을 넣기 전 상태의 최적값이다.i-1을 참조하므로 같은 물건을 중복 사용하지 않는다.- 1차원 배열로 최적화할 수도 있다. 이 경우 j를 역순으로 순회해야 한다.
복잡도
- 시간: O(N × K)
- 공간: O(N × K) — 1차원 최적화 시 O(K)
DP의 가장 기본이 되는 문제, 점화식의 의미를 정확히 이해하는 것이 중요하다.
댓글