본문 바로가기

Problem Solving/BaekJoon

2624 동전 바꿔주기

 

 

2624번: 동전 바꿔주기

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을

www.acmicpc.net

전형적인 DP 문제이다.

이차원 배열 dp를 만들고 dp[i][j]에는 i번째 동전까지 사용했을 때, j원을 만들 수 있는 가능한 경우의 수를

저장하는 방식으로 해결했다.

 

C++

더보기
#include <iostream>
#include <vector>

using namespace std;

int cnt, k;

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

	int t;
	cin >> t >> k;
	vector<pair<int, int>> vec(k + 1);
	vector<vector<int>> dp(k + 1, vector<int>(t + 1));

	for (int i = 1; i <= k; ++i)
		cin >> vec[i].first >> vec[i].second;

	dp[0][0] = 1;
	for (int i = 1; i <= k; ++i) {
		for (int j = 0; j <= t; ++j) {
			for (int k = 0; k <= vec[i].second; ++k) {
				if (j - k * vec[i].first >= 0)
					dp[i][j] += dp[i - 1][j - k * vec[i].first];
				else
					break;
			}
		}
	}

	cout << dp[k][t];

	return 0;
}
728x90

'Problem Solving > BaekJoon' 카테고리의 다른 글

2056 작업  (0) 2021.02.06
1987 알파벳  (0) 2021.02.02
1806 부분합  (0) 2021.02.02
2228 구간 나누기  (0) 2021.01.15
4386 별자리 만들기  (0) 2021.01.15