[Algorithm] Baekjoon 2293번 : 동전 1

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

2293번: 동전 1

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    vector<int> coins;
    int n, k, temp;
    int dp[100001] = { 0 };
 
    cin >> n >> k;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> temp;
        coins.push_back(temp);
    }
 
    dp[0] = 1;
 
    for (int i = 0; i < n; ++i) // 동전갯수.
    {
        // 동전단위 선택
 
        for (int j = coins[i]; j <= k; ++j) // 선택된 동전단위부터 시작. 그것보다 아래면 쓸수조차없으니까.
        {
            dp[j] += dp[j - coins[i]];
        }
    }
    
    cout << dp[k];
}

간단한 DP문제같은데 풀이를 봐도 쉽게 이해가 되지않았다가, 이제 좀 알것같은 문제.

일단 동전관련 문제는 되는대로 풀면서 내가 이해한 방식이 맞는지 확인해봐야 할 것 같다.