평범한 배낭 (feat. 백준 12865번)

평범한 배낭
https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/12865
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	register int N, K, arr[101][2], dp[101][100001] = { 0 };
	cin >> N >> K;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i][0] >> arr[i][1];
	for (register int i = 1; i <= N; ++i)
		for (register int j = 1; j <= K; ++j)
			if (arr[i][0] <= j)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - arr[i][0]] + arr[i][1]);
			else
				dp[i][j] = dp[i - 1][j];
	cout << dp[N][K] << endl;
	return 0;
}
// *&)*@*

1. N=1일때를 보면 dp[1][1] ~ dp[1][5] = 0, dp[1][6] = dp[0][6 - 6] + arr[1][1], dp[1][7] = dp[0][7 - 6] + arr[1][1] 인 것을 알수 있고, 여기서 arr[1][1] 는 13입니다.
2. N=2일때를 보면 dp[2][1] ~ dp[2][3] = 0, dp[2][4] = dp[1][4 - 4] + arr[1][1], dp[2][5] = dp[1][5 - 4] + arr[1][1], dp[2][6] = dp[1][6-4] + arr[1][1], dp[2][7] = dp[1][7 - 4] + arr[1][1] 인 것을 알수 있고, 여기서 arr[1][1] = 8입니다.
3. N=3일때를 보면 dp[3][1] ~ dp[3][2] = 0, dp[3][3] = dp[2][3 - 3] + arr[1][1], dp[3][4] = dp[2][4 - 3] + arr[1][1], dp[3][5] = dp[2][5 - 3] + arr[1], dp[3][6] = dp[2][6 - 3] + arr[1][1], dp[3][7] = dp[2][7 - 3] + arr[1][1] 인 것을 알수 있고, 여기서 arr[1][1]은 6, dp[3][7] = dp[2][4] + 6 = 8 + 6 = 14 가 됩니다.