728x90
문제
https://www.acmicpc.net/problem/2293
문제이해
- 첫째 줄에 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);
}
728x90
'Coding' 카테고리의 다른 글
[C++]백준 7576번: 토마토 (0) | 2023.07.21 |
---|---|
[C++]백준 1697번: 숨바꼭질 (0) | 2023.07.21 |
[C++]백준 1932번: 정수 삼각형 (0) | 2023.07.18 |
[C++]백준 1522번: 문자열 교환 (0) | 2023.07.17 |
[C++]백준 11651번: 좌표 정렬하기 2 (0) | 2023.07.17 |