백준 Gold 5 Coins

Coins (백준 Gold 5)

https://www.acmicpc.net/problem/3067

t개의 테스트 케이스가 주어진다

N개의 동전값이 주어지고, M이라는 목표 금액이 주어졌을때
M 값을 만들 수 있는 경우의 수를 출력하는 문제

풀이 방법

배낭 문제와 다소 비슷하지만 다르다

• 양 문제 모두, 특정 용량을 채우는 문제
  

• dp 테이블 구조가 같음
  

// 물체가 1개만 존재하는 경우의 배낭문제 (0/1)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

// 물체가 무한대로 존재하는 코인 문제 (경우의 수)
dp[j] += dp[j - coin[i]];

• 다만, 0/1 배낭문제와는 다르게 ‘경우의 수’를 세는 방식이며
  동전을 ‘무한’으로 사용 가능하기에
  오름차순으로 목표값에 도달하게 한다
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	while (t > 0)
	{
		int n;
		cin >> n;

		vector<int> coins(n);
		for (int i = 0; i < n; i++)
			cin >> coins[i];

		int m;
		cin >> m;

		vector<int> dp(m + 1);

		for (int i = 0; i < n; i++)
		{
			dp[coins[i]] += 1;

			for (int j = coins[i]; j <= m; j++)
			{
				dp[j] += dp[j - coins[i]];
			}
		}

		cout << dp[m] << '\n';

		t--;
	}

	return 0;
}

결과