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

#include<iostream>
#include<algorithm>
 
int DP[101][100001] = {};
int W[101] = {};
int V[101] = {};
 
int main()
{
	int N = 0;
	int K = 0;
	std::cin >> N >> K;
 
	for (int i = 1; i <= N; ++i)
	{
		std::cin >> W[i] >> V[i];
	}
 
	// i번째 물품
	for (int i = 1; i <= N; ++i)
	{
		// j번째 무게
		for (int j = 1; j <= K; ++j)
		{
			// j 만큼에서 들어갈 수 있다면 
			// DP[i - 1][j - W[i]](i번째 물품 무게를 뺀 최댓값) + V[i](가치값) 
			if (j - W[i] >= 0) 
                DP[i][j] = std::max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
 
			// 아니라면 이전 것 그대로
			else 
				DP[i][j] = DP[i - 1][j];
		}
	}
 
	std::cout << DP[N][K];
}

DP로 계산, 2차 배열로 갯수, 무게, 가치 따로 나눠서 계산해야한다.

2중 배열로 만들고 i, j 를 갯수, 무게로 나눴고 값을 가치로 매겼다