문제링크
https://www.acmicpc.net/problem/2293
문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.
조건
- 시간 제한 : 0.5s
- 메모리 제한 : 4MB
해설
https://sihyungyou.github.io/baekjoon-2293/ 를 참고하였습니다! ㅠㅠㅠ
K=8일때 동전의 값들이 1/2/5라고 해보자.
1로 만들 수 있는 경우의 수
1 2 3 4 5 6 7 8
dp : 1 1 1 1 1 1 1 1
1, 2로 만들 수 있는 경우의 수
1 2 3 4 5 6 7 8
dp : 1 2 2 3 3 4 4 5
1, 2, 5로 만들 수 있는 경우의 수
1 2 3 4 5 6 7 8
dp : 1 2 2 3 4 5 6 7위 값들을 만드는 데에는 다음의 식을 따른다. dp[i] = dp[i] + dp[i-n] 1, 2, 5를 이용해 7을 만드는 경우를 가정해보면, 7을 만드는 경우의 수 = 1, 2를 이용해 7을 만드는 경우의 수 + 5를 추가하여 7을 만드는 경우의 수 ( = 2를 만드는 경우의 수 )와 같다. 따라서, 5를 추가한다면 dp[7] 의 값에 dp[7] + dp[7-5]이 대입된다.
풀이
입력받은 동전의 가치를 오름차순으로 정렬하여 작은 값부터 dp를 구할 수 있게 해주었다.
for(int i = 0; i < N; i++) {
cin >> coin[i];
}
sort(coin.begin(), coin.end());
위에 나온 식인 dp[i] = dp[i] + dp[i-n]를 코드로 옮기면 아래와 같다.
for(int i = 0; i < N; i++) {
for(int j = 0; j < K+1; j++) {
if(j-coin[i] >= 0) {
dp[j] += dp[j-coin[i]];
}
}
}
여기에서 1, 2, 5같은 앞에 나온 값과 상관없이 추가되는 단일 동전으로 구성된 경우의 수를 추가해주기 위해서, 현재 추가하고있는 동전의 가치와 dp의 index가 같다면 (5원을 추가하는데 5원을 구성하는 경우의 수 계산 중일 때) 동전 하나로 구성이 가능하므로 1을 추가해주는 코드를 삽입해야 한다.
for(int i = 0; i < N; i++) {
for(int j = 0; j < K+1; j++) {
if(j-coin[i] >= 0) {
dp[j] += dp[j-coin[i]];
}
if(coin[i] == j) {
dp[j] += 1;
}
}
}
위 반복문을 수행하고 나면 원하는 결과인 K원은 dp[K]에 저장되어있다. 이를 출력해주면 된다.
cout << dp[K];코멘트
열심히 고민을 했지만, 풀이를 보고 말았다. 내가 생각했던 방식에서 한 발 만 더 나갔으면 된거였는데, 그 한 발을 움직이는게 쉽지 않았던 것 같다. 이거 쉬운 문제같은데... 벌써부터 이러면 어떻게 하냐 ㅠㅠ
고민
분명 쉬운 문제인데, 중복을 제거해야한다는 조건이 생각을 복잡하게 만들었던 것 같다. 또, top-down으로 풀어야 한다는 생각에 사로잡혀서 8 = 1+7 / 2+ 6 / 5+3 으로 계속 생각하다보니 자꾸 반복을 제거하지 못해서 꼬였던 것 같다. bottom-up으로 푸는 방법에 대해서도 계속 고려를 해보자.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, K;
cin >> N >> K;
vector<int> coin(N);
vector<int> dp(K+1, 0);
for(int i = 0; i < N; i++) {
cin >> coin[i];
}
sort(coin.begin(), coin.end());
for(int i = 0; i < N; i++) {
for(int j = 0; j < K+1; j++) {
if(j-coin[i] >= 0) {
dp[j] += dp[j-coin[i]];
}
if(coin[i] == j) {
dp[j] += 1;
}
}
}
cout << dp[K];
return 0;
}
Uploaded by Notion2Tistory v1.1.0