2293 동전 1

2293. 동전 1 / c++ / Gold5 / 실패

문제

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

1. 각각 가치가 다른 동전이 N개의 종류가 있다고 할 때,
2. 가치 K를 만들 수 있는 경우의 수는? (순서만 다른 것은 같은 경우)

접근 방식

동적 프로그래밍

1. DP 는 보통 dp[i] = dp[i] + dp[target-i] 의 구조를 가지므로 그렇게 생각해봤다.
2. 그런데 동전이 순서만 다른 경우를 제거할 방법이 떠오르질 않았다.
3. 문제 풀이 시간이 30분이 초과되어 다른 분의 코드를 참고하였다.
4. 이 경우 dp[i] += dp[target-i]의 구조를 가진다.
5. dp[0] (어떤 동전도 사용하지 않는 경우)를 1로 두고,
6. 만약 가치1인 동전이 주어진다면 i를 1부터 K까지 dp[i] += dp[i-1]을 해주는 것이다. (직전 가치를 만드는 경우의 수를 더해준다. 왜? 현재 동전의 가치가 1이므로)
7. 즉, 가치가 5인 동전이 주어진다면 최소 5부터 (5 + 0 = 5 이므로) 최대 K까지 다시 dp[i] = dp[i-5]를 해주는 것이다. (만약 이 때 5가 제일 가치가 작은 동전이었다면 dp[0] = 1 이므로, dp[5] = 1이 된다. 5짜리 동전 하나만으로 만든 경우)

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;

int N, K, num;
int dp[10'001] = {};

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;

    dp[0] = 1;

    for (int i = 0; i < N; ++i)
    {
        cin >> num;
        for (int j = num; j <= K; ++j)
        {
            dp[j] += dp[j - num];
        }
    }

    cout << dp[K] << '\n';

    return 0;
}

다시 생각해 볼 점

1. dp는 재귀를 통해 dp[i] = dp[i-j] + dp[j]와 같은 경우만 있다고 생각했다.
2. 그런데 이 처럼 중복이 없는 경우에는 for문으로 dp[i] += dp[i-value]로 처리할 수 있다는 것을 깨달았다.
3. 일단 dp는 기다란 테이블을 하나 놓고 거기서 어떻게 문제를 풀어나갈 지를 고민해보는 것이 좋겠다.