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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k;
int d[100001];  // 가방 용량
vector<pair<int, int>> wv;	//물건의 무게, 가치

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

	cin >> n >> k;

	wv.push_back({ 0 , 0 });
	for (int i = 1; i <= n; i++)
	{
		int temp1, temp2;
		cin >> temp1 >> temp2;
		wv.push_back({ temp1 , temp2 });	//무게, 가치
	}

	for (int i = 1; i <= n; i++) {
		for (int j = k; j >= 1; j--) {
			if (wv[i].first <= j) {
				d[j] = max(d[j], d[j - wv[i].first] + wv[i].second);
			}
		}
	}

	cout << d[k];
}

 

풀이

1. 가방의 용량만큼에서 1~k까지의 최대가치를 순서대로 넣는다.

2. 무게별의 가치를 다 저장하고 그 해당 k의 가치를 출력한다.

 

 

d[7] < d[7 - 6] + 13  0     <     0       +  13 d[7] = 13	d[7] < d[7 - 4] + 8 13     >     0        + 8 d[7] = 13	d[7] < d[7 - 3] + 6 13     <     8      +  6 d[7] = 14
d[6] < d[6 - 6] + 13 0     <     0        + 13 d[6] = 13 다음 무게로->	d[6] < d[6 - 4] + 8 13     >     0      + 8 d[6] = 13	...
	d[5] < d[5 - 4] + 8 0     <     0      + 8 d[5] = 8
	d[4] < d[4 - 4] + 8 0     <     0      + 8 d[4] = 8 다음 무게로->

 

이런식으로 계산하게되어 결국 d[7]에서 6이 가졌던 13이

d[4]와 wv[3]값을 합친 14가 d[7]의 최대 값으로 가게된다.

 

 

기타

- 최대n(101)*m(100001)번 반복하게된다.