BOJ 2293번 : 동전 1

dp를 푸는데 가장 중요한건 두개인 것 같다. 첫번째는 초기값 설정, 두번째는 점화식 세우기...

 

처음 이 문제를 풀때는 초기값과 점화식이 정확하지 않아 중복이 일어나는 현상이 일어났다... 문제는 중복값을 제거 해주는 숫자가 뭔가.. 규칙성이 없었다는것.... 그때 빨리 포기 하고 다른 방법을 찾았어야 하는데 뭔가 될듯 말듯 한 느낌에 붙들고 있다가 포기하고 찬찬히 보니 경우 규칙이 보였다.

 

처음 이 문제를 푸는 사람도 비슷할 것이라고 생각한다. 중복 제거 문제.... 오늘 또 한가지를 배웠다. 중복이 일정한 규칙이 없는것 같으면, 분명히 다른 방법이 있을 것이다.....

 

본론으로 돌아와서! 문제를 처음 읽었을때, "경우의 수"를 구하라는 것이 먼저 보인다. 그 말인 즉슨, dp 배열에 값이 아닌, 경우의 수 가 들어가야 한다는 것.

 

처음엔 규칙이 보이지 않아 일단 예제에 나온 것을 모두 적어보았다. 하지만, 규칙을 세우기에는 너무 불규칙적이고, dp 처럼 풀기에는 중복제거가 너무 이상했다. 그래서 애초에 중복이 일어나지 않게 동전이 1개씩 추가 될 경우로 다시 적어보았다.

 

1원, 2원, 5원으로 10원을 만들때 까지의 상태는 다음과 같았다.

0원을 만들때는 무시하고, 1원으로는 10원까지 모두 1가지 방법이 있다.

 

2원이 추가 되었을때를 적어보면, dp[n] = dp[n]+dp[n-2] 가 되는것을 알 수 있다.

이때 dp[2] = dp[2]+dp[0]을 위해 dp[0]을 1로 가정하면 모두 들어맞게 된다.

 

5원이 추가 되었을 때는, dp[n] = dp[n]+dp[n-5] 이다.

 

규칙을 찾았다.... 가장 애 먹었던 초기값 설정은, 가장 가치가 작은 동전으로 각 원을 만들수 있는 경우의 수 였다.

 

<소스코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    int n, k = 0;
    cin >> n >> k;
    vector<int> dp(k+1, 0);
    vector<int> coin(n);
    for (int i = 0; i < n; i++)
        cin >> coin[i];
    sort(coin.begin(), coin.end());
    for (int j = 0; j < k + 1; j++) { // 제일 작은 동전으로 초기화
        if (!(j%coin[0])) {
            dp[j]++;
        }
    }
    for (int i = 1; i < n; i++) {                // 다음 동전이 추가 되었을때 계산
        for (int j = coin[i]; j < k + 1; j++) {
            dp[j] = dp[j] + dp[j - coin[i]];
        }
    }
    cout << dp[k];
}

문제 : 

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

2293번: 동전 1