[백준] 2293번 동전 1 C++

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

C++

#include<iostream>
#include<algorithm>
using namespace std;

// 첫번째는 정렬해서 큰 동전부터 최대한 많이 사용하면서 넘어가려고 했는데 시간초과 무조건 발생
// 그래서 작은 동전부터 차례대로 계산하는 dp 방식 생각
// 10원을 만들려면 예를 들어 2원 사용하면 8원 만드는 방식에 +2하면 되니까 8원 경우의수 +1이다
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,k;
    cin >> n >> k;
    int coin[n];
    int dp[10001] = {0};
    dp[0] = 1; // 0원 만들 수 있는건 1가지

    for(int i = 0; i < n; i++) {
        cin >> coin[i];
    }
    
    // 10원을 만들려면 9원 만드는방법에 1원 방법 더해주고 8원 만드는방법에 2원 방법 더해주고 이런식으로 진행하면된다.
    for(int j = 0; j < n; j++) {
        for(int t = coin[j]; t <= k; t++) {
            dp[t] += dp[t - coin[j]];
        }
    }
    cout << dp[k] << "\n";
}

문제풀이

• 먼저 입력받을 코인의 가치 배열과 k원을 만들 수 있는 경우의 수가 담긴 dp 배열을 생성했다. 그런 다음 dp배열에 t - coin[j]의 경우의 수를 계속해서 더해줬다. 예를 들어서 k = 10, 가치 1,2,5일 경우 1은 9일 때 경우의수를 더해주면 되고 2일 때는 8일 때의 경우의 수를 더해주면 된다. 이런식으로 dp[t]의 값을 계속해서 더해주면서 최종 dp[k]의 경우의수를 구했다. t 변수를 coin[j]로 초기화한 이유는 중복을 발생시키지 않게 하기 위해서이다.

Comment

• 처음에는 가치가 가장 높은 순으로 동전을 오름차순한 뒤 k넘을 때까지 for문 돌리면서 높은 순서대로 동전을 사용하는 알고리즘이 생각났다. 하지만 이 문제의 제한시간은 0.5초이기 때문에 무조건 시간초과가 발생할 것이라고 생각했다. 그런 다음 k = 1,2,3,.. 일 때 어떤 경우의 수가 나오는지 다 적어봤을 때 k원의 경우의수를 구하기 위해서는 k - coin[...]의 경우의 수를 dp[...]에 더해주면 된다는 것을 알게되었다.
  확실히 dp 문제는 어려워,,,, 많이 적고 수학적 사고력이 많이 필요하다