백준 15817 c++ : DP, 배낭문제

각 물건의 개수가 하나인 다른 배낭 문제와 다르게 개수가 여러개 지정되어 있어서 고려해야 한다.

#include <iostream>
#include <vector>

using namespace std;

void input_data(int* N, int* x, vector<pair<int, int>>& pipe) {
	cout << "input_data()\n";
	int i, L, C;

	cin >> *N >> *x;
	for (i = 0; i < *N; i++) {
		cin >> L >> C;
		pipe.push_back({ L, C });
	}

	return;
}

int find_answer(int N, int x, vector<pair<int, int>>& pipe) {
	cout << "find_answer()\n";
	int answer = 0;
	int i, j, k;
	vector<int> DP(x + 1, 0);
	int L, C;

	//pipe[i].first는 파이프의 길이
	//pipe[i].second는 해당 길이 파이프의 개수
	//파이프들을 활용해 길이 x를 만들 수 있는 방법의 수?
	DP[0] = 1;
	for (i = 0; i < N; i++) {
		L = pipe[i].first;
		C = pipe[i].second;

		for (j = x; j >= L; j--) {
			for (k = 1; k <= C; k++) {
				if (j - L * k >= 0) {
					DP[j] += DP[j - L * k];
				}
				else {
					break;
				}
			}
		}

		for (j = 1; j <= x; j++) {
			cout << DP[j] << " ";
		}
		cout << "\n";
	}
	answer = DP[x];

	return answer;
}

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

	int N, x;
	vector<pair<int, int>> pipe;

	input_data(&N, &x, pipe);
	cout << find_answer(N, x, pipe) << "\n";

	return 0;
}