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

 

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

2293번: 동전 1

 

 

 

 

 

---

- 문제

 

  동전의 값이 n개 주어지면 이 동전들을 이용해서 k원을 만들 수 있는 경우의 수를 구하는 문제다(중복없이).

 

 

---

- 해설

이건 나도 혼자서 못 풀어서 다른 사람 풀이를 보고 참고했다.

 

1, 2, 5원이 있다고 할 때 dp라는 배열에 1을 이용했을 때 만들 수 있는 경우의 수를 저장하고

 

그 다음 반복문에서 2도 함께 사용했을 때, 즉 1과 2를 사용했을 때 만들 수 있는 경우의수를 더한다.

 

마지막 5도 마찬가지로 반복해서 풀었다.

 

다른 사람 블로그를 이렇게 가져와도 되는 지 모르겠지만,

 

https://danidani-de.tistory.com/5

여기 내용을 많이 참고했다.

---

- 풀이

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, k, temp;
    cin >> N >> k;
    vector<int> coins(N);
    vector<int> dp(k + 1);
    for (int i = 0; i < N; i++)
    {
        cin >> coins[i];
    }
    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];

    return 0;
}

 

 

---

- 새롭게 알게 된 점