[백준] 3067_Coins C++

25 Dec 2023 in Study on Coding Test

DP, 배낭문제를 쓰는 문제

정답제출코드

#include <iostream>
#include <vector>
#include <cstring>

#define MAX 10001

using namespace std;

int T, N, M;
int cnt_array[21];
int DP[MAX];

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

	cin >> T;

	for (int i = 0; i < T; ++i)
	{	
		cin >> N;

		memset(DP, 0, sizeof(DP));
		DP[0] = 1;

		vector<int> Coins;
		Coins.push_back(0);
		for (int j = 0; j < N; ++j)
		{
			int _input;
			cin >> _input;
			Coins.push_back(_input);
		}

		cin >> M;

		for (int i = 1; i <= N; ++i)
		{
			for (int j = 1; j < MAX; ++j)
			{
				if (j - Coins[i] >= 0)
					DP[j] += DP[j - Coins[i]];
			}
		}

		cout << DP[M] << '\n';
	}

	return 0;
} 

DP배열을 만든다.

이것은 i번째 동전을 가져갔을 때 j원을 만들 수 있는 방법의 가짓수를 말한다.

그리고 첫 번째 동전부터, 1원부터 10,000원까지, 현재 동전의 값만큼을 더해서 j원이 나올 수 있는지 판단하고,

나올 수 있다면 j-Coin[i]원을 만들 수 있는 방법의 가짓수를 j원을 만들 수 있는 방법의 가짓수에 더해준다.

마지막으로 DP[M], 즉 M원을 만들 수 잇는 가짓수를 출력한다.