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

2293번: 동전 1

문제 요약

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
• 출력: 첫째 줄에 경우의 수를 출력한다. 경우의 수는 $2^{31}$보다 작다. ``` 예제1

입력 3 10 1 2 5 출력 10

## 풀이
동적계획법을 사용하면 된다. 이중 for문으로 동전 한개씩 k까지 만들수 있는 것들을 전부 구하면 된다.

## 어려웠던 점
처음에는 이중dp를 짜서 했는데 메모리초과가 났다 일중dp로도 풀 수 있었다.

## 배운 점 / 느낀 점
일중으로 짤 수 있는건 일중으로 짜자

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int n, k;
vector<int> coins;
vector<int> dp;

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

    cin >> n >> k;
    coins = vector<int>(n);
    dp = vector<int>(k+1, 0);
    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;
}