백준 17845 c++ : 배낭문제

배낭 문제는 DP라고 생각하고 예시에 따라 표를 작성해야 한다.

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

using namespace std;

void input_data(int* N, int* K, vector<pair<int, int>>& list) {
	cout << "input_data()\n";
	int i, I, T;

	cin >> *N >> *K;
	for (i = 0; i < *K; i++) {
		cin >> I >> T;
		list.push_back({ I, T });
	}
	
	return;
}

int find_answer(int N, int K, vector<pair<int, int>>& list) {
	cout << "find_answer()\n";
	int i, j;

	vector<vector<int>> dp(K+1, vector<int>(N+1, 0));
	for (i = 1; i <= K; i++) 
	{
		for (j = 1; j <= N; j++) 
		{
			if (j < list[i-1].second) {
				dp[i][j] = dp[i-1][j];
			}
			else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j - list[i -1].second] + list[i-1].first);
			}
		}

		for (j = 1; j <= K; j++) {
			for (int k = N - 10; k <= N; k++) {
				cout << dp[j][k] << "\t";
			}
			cout << "\n";
		}
		cout << "\n";
	}

	return dp[K][N];
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, K;
	vector<pair<int, int>> list;

	input_data(&N, &K, list);
	cout << find_answer(N, K, list) << "\n";

	return 0;
}