문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.
7달 전 맞았던 코드입니다.
#include<bits/stdc++.h>
using namespace std;
int arr[2][10001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int>num;
int n, k, x;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> x;
num.push_back(x);
}
sort(num.begin(), num.end());
arr[0][0] = 1; arr[1][0] = 1;
for (int i = 1; i <= k; i++) {
if (i % num[0] == 0) {
arr[0][i] = 1;
}
else
arr[0][i] = 0;
}
int sum = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= k; j++) {
for (int l = 0; l <= j / num[i]; l++) {
sum += arr[0][j - num[i] * l];
}
arr[1][j] = sum;
sum = 0;
}
for (int j = 1; j <= k; j++) {
arr[0][j] = arr[1][j];
}
}
cout << arr[0][k];
}
i번째 동전까지 사용할 수 있을때, j원을 만들때
i번째 동전을 0개,1개,,,,,,n개 사용하고 i-1번째 동전까지 사용할 수 있는 값을 모두 더했습니다.
복잡하고, 코드도 너무 길었습니다.
심지어 메모리까지 초과해서 dp2차원배열을 n*k에서 2*k로 줄여 간신히 통과했습니다.
새로운 코드입니다. 너무너무 간단합니다......................................
#include<iostream>
using namespace std;
int dp[10001];
int main() {
dp[0] = 1; //x원의 동전을 사용했을때, 채워야할 나머지금액이 없는경우의 수는 1입니다.
int n, k, x;
cin >> n >> k;
while (n--) {
cin >> x;
for (int i = x; i <= k; i++) {
dp[i] += dp[i - x]
//while문을 한번 돌 때마다, 사용할 수 있는 동전의 종류는 하나 늘어납니다. (입력됨)
//dp[i]는 i원을 만들기 위한 경우의 수 입니다.
//매번 while문에서, dp[i]+=dp[i-x]를 수행합니다.
//dp[i-x]는 동전x를 하나 사용했을때, 나머지 i-x원을 만드는 경우의 수 입니다.
//dp[i-x]도 동전 x를 하나 사용했을 때 경우의 수를 포함하므로, 결국 배열dp는 동전 x를 몇개든 사용한 데이터를 포함합니다.
}
}
cout << dp[k];
}
각 while문 마다, 동전x를 사용합니다. dp[x]부터 dp[k]까지만 갱신할 수 있으므로 for문은 i=x부터 x<=k까지 돕니다.
dp[i]는 동전x를 사용해 i원을 만들 수 있는 경우의 수인데, 기존 dp[i]값에 dp[i-x]를 더하면 동전 x를 하나 사용했을 때, 나머지 금액을 채우는 경우의 수를 더하게 됩니다.
i는 x부터 k까지이므로,,,,
i가 2*x 또는 n*x 보다 커지게 되는 경우 dp[i-x]는 이미 갱신된 값입니다. 따라서, 동전x를 하나만 더 사용했을때의 경우의 수만 더해주어도 dp[k]는 모든 경우의 수를 더하게 됩니다.
'baekjoon' 카테고리의 다른 글
[백준] 11054 가장 긴 바이토닉 부분 수열 + 11053 가장 긴 증가하는 부분수열 + lower_bound (1) | 2022.12.28 |
---|---|
[백준]2294 동전2 (수정 + 최적화) (0) | 2022.12.28 |
[백준] 2096 내려가기 (복습) (0) | 2022.12.28 |
[백준] 2589 보물섬 (복습) + Structured Binding in C++17 with Tuple (1) | 2022.12.27 |
[백준] 2660 회장뽑기 (복습) + 큐를 사용하는 두가지 방법 (0) | 2022.12.27 |