[BOJ] 2293. 동전 1
동전 1
알고리즘 구분 : 다이나믹 프로그래밍
문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.
예제 입력 1
3 10
1
2
5
예제 출력 1
10
문제 풀이
일단 바텀업방식으로 초반의 index에서 계산하였던 결과를 후반의 index에서 활용해야 한다고 판단하여, DP로 접근하였다.
그러나, 처음에는 dp[3] = (dp[0] dp[3]) + (dp[1] dp[2])와 같이, k를 만든다고 하면, k를 만들 수 있는 경우의 수를 찾아, 이들끼리의 곱을 더하는 방식으로 점화식을 구현해서 예제에 적용해보았으나 일치하지 않았다. 위의 점화식이 가지고 있는 오류는 아래와 같다.
n = 2, k = 4 / 동전 value : 1, 2
위와 같은 조건에서, dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 2가 되어야 하는데, dp[2]값 자체가 위의 점화식에서 제대로 갱신되지 않았다. 또한 dp[4]를 구하는 과정에서 보았을 때, 동전의 가치가 1인 동전으로만 4를 만드는 경우의 수가 중복으로 더해져 dp[4]의 값이 원래 나와야 하는 결과보다 큰 값을 가진다.
내가 'X원'짜리를 활용해서 특정 금액을 만드는 과정이라면, 최소한 그 금액은 X원보다 크거나 같아야 한다. 예를 들어, 3원짜리 동전을 가지고 어떤 금액을 만들 때, 1원이나 2원을 만들 수 없다는 의미이다. 그 부분을 고려하여 점화식을 다시 만들게 되면, dp[Y] = dp[Y] - dp[Y - X]가 된다. 즉, X원을 활용해 Y원을 만들기 위해서는, Y - X원을 만드는 경우의 수를 더해주면 된다는 것이다. 이를 구현 과정에서 적용한다면, 이중 반복문을 사용하여, 첫 번째 반복문의 변수는 배열의 index를 지정하는 데 활용하며, 두 번째 반복문의 변수는 만들어가는 동전의 가치를 찾는데 활용한다.(즉, Y로 활용된다는 의미이다.)
시간복잡도를 단순하게 생각한다면, O(NK)가 되지만, 두 번째 반복문의 시작점이 0이 아닌 해당 index에서의 동전의 가치이기에, 실제 시간복잡도는 O(NK)보다 작을 것이다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> v(101);
int dp[10001];
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i < n + 1; i++) {
cin >> v[i];
}
solve();
return 0;
}
void solve() {
dp[0] = 1;
if(v[0] > k) {
cout << 0 << endl;
}
else {
for(int i = 1; i < n + 1; i++) {
for(int j = v[i]; j < k + 1; j++) {
dp[j] = dp[j] + dp[j - v[i]];
}
}
}
cout << dp[k] << endl;
}
- 문제 출처 : https://www.acmicpc.net/problem/2293
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
Author And Source
이 문제에 관하여([BOJ] 2293. 동전 1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dl-00-e8/BOJ-2293.-동전-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)