백준 3067 c++

코딩 테스트 대비용 냅색문제 풀이를 시작한다.

#include <iostream>
#include <vector>

using namespace std;

void input_data(vector<int> &coin, int *M) 
{
	int N, C;
	int i;

	cin >> N;
	for (i = 0; i < N; i++)
	{
		cin >> C;
		coin.push_back(C);
	}
	cin >> *M;

	return;
}

void find_answer(vector<int> &coin, int M) 
{
	int N = coin.size();
	vector<int> dp(10001, 0);
	int i, j;

	dp[0] = 1;
	for (i = 0; i < N; i++)
	{
		for (j = coin[i]; j <= M; j++)
		{
			dp[j] += dp[j - coin[i]];
		}
		cout << "i : " << i << " dp[M] : " << dp[M] << "\n";
	}
	cout << dp[M] << "\n";

	return;
}

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

	int T;

	cin >> T;
	while (T)
	{
		vector<int>coin;
		int M;

		input_data(coin, &M);
		find_answer(coin, M);

		T--;
	}

	return 0;
}