[C++]백준 2293번: 동전 1

문제

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

2293번: 동전 1

 

문제이해

• 첫째 줄에 n과 k를 입력한다.
• 두 번째 줄부터 n개의 동전에 대한 가치가 주어진다.
• n개의 동전으로 k를 만들 수 있는 경우의 수를 출력한다.

이 문제는 n개의 전부다 가치가 다른 동전들을 사용하여 k를 만들어 내는 경우의 수를 출력해야 되는 문제이다.

 

이 문제를 해결하기 위해서는 다이나믹 프로그래밍을 사용해야 한다. 문제에 나와있는 예시를 통해 설명해 보겠다.

가치가 1인 동전을 사용하여 1부터 8까지의 목표를 만드는 경우의 수는 다음과 같다.

가치\목표	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2
5

1원을 만들기 위해서는 1

2원을 만들기 위해서는 1 + 1

3원을 만들기 위해서는 1 + 1 + 1

.

.

.

따라서 모든 목표에 대한 경우의 수는 1이다.

다음은 누적하여 가치를  2인 동전을 사용하여 목표를 만드는 경우의 수이다.

가치\목표	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5
5

1원을 만들기 위해서는 1

2원을 만들기 위해서는 1 + 1 또는 2

3원을 만들기 위해서는 1 + 1 + 1 또는 2 + 1

4원을 만들기 위해서는 1 + 1 + 1 + 1도는 1 + 1 + 2 또는 2 + 2

.

.

.

다음은 계속해서 5인 동전을 사용하여 목표를 만드는 경우의 수이다.

가치\목표	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2	1	2	2	3	3	4	4	5
5	1	2	2	3	4	5	6	7

1을 만들기 위해서는 1

.

.

.

5를 만들기 위해서는 1 + 1 + 1 + 1 + 1 또는 1 + 1 + 1 + 2 또는 1 + 2 + 2 또는 5

.

.

.

배열을 통해 다시 정리해 보자. c [i]는 i번째 동전을 의미하고 s [n] = k 는 n을 만들기 위한 경우의 수는 k라는 것을 의미합니다. 위의 정리를 토대로 s[n] = s[n] + s [a - c [i]]라는 것을 알 수 있습니다.

 

다음은 그대로 코드로 작성한 결과입니다.

 

문제풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> s(10000);

int sums(int n, int k, vector<int> c) {
	s[0] = 1;
	for (int i{ 0 }; i < n; i++)
		for (int a{ c[i] }; a <= k; a++)
			s[a] = s[a] + s[a - c[i]];
	return s[k];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	vector<int> coins(n);
	for (int i{ 0 }; i < n; i++)
		cin >> coins[i];
	cout << sums(n, k, coins);
}