[1일 1알고] G4 2294 동전 1

 

유명한 dynamic programming문제인 동전 문제입니다.

이전의 동전2문제와 다르게 

https://basaeng.tistory.com/125

[1일 1알고] G5 2294 동전 2

이번 문제는 특정 숫자 K를 위한 최소 동전의 개수가 아닌 K를 만들 수 있는 경우의 수를 계산합니다.

 

여기서 중요한 것은 경우의 수는 순서를 고려하지 않는 것입니다. 

예를 들어 3을 만들 때 1+2와 2+1은 같은 경우의 수입니다.

---

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

    int N, K;
    cin >> N >> K;

    vector<int> coins(N, 0);
    vector<int> dp(K + 1, 0);

    for (int i = 0; i < N; ++i)
    {
        cin >> coins[i];
    }

    dp[0] = 1;
    for (int j = 0; j < N; ++j)
    {
        for (int i = coins[j]; i <= K; ++i)
        {
            dp[i] += dp[i - coins[j]];
        }
    }

    cout << dp[K];
    return 0;
}

 

코드 자체는 매우 간단하게 나왔습니다. 

 

동전을 배치하는 경우의 수를 각 동전마다 계산해 합산하면 K를 만들 수 있는 조합을 구할 수 있습니다.

 

만약 i와 j의 루프를 바꾼다면 조합이 아닌 순열의 개수를 구할 수 있습니다.