[C++] 2293 - 동전 1 (골드5)

1. 문제 설명

2293번: 동전 1

파이썬이 너무 느려터져서 C++로 갈아타서 처음 풀어본 게 이 문제였다.

C++은 예전에 1주일 정도 공부해본 게 다라 익숙하질 않아서 적응하는데 시간을 더 많이 소비했다.

코드 짤 땐 미친듯이 에러가 나서 화나는데 제출했을 때 0s 뜨면 그렇게 기분이 좋을 수가 없다.

 

---

2. 아이디어

아이디어는 어렵지 않다. 전형적인 DP 문제라는 걸 쉽게 알 수 있을 것이다.

주어진 각 동전으로 k원을 만들 수 있는 경우의 수를 차례로 탐색한다.

 

1원을 이용해서 10원을 만들어야 한다면 1부터 10까지 모든 경우의 수는 1씩 추가된다.

그 다음 동전이 2원이면 10까지의 수 중 2의 배수에 1씩 추가한다.

문제는 이렇게 하면 3원을 만들기 위해 1과 2를 섞어쓸 수 있는 경우는 고려하지 않게 된다.

따라서 dp[(현재 비용)]의 경우의 수를 dp[(현재 비용) - (동전)]으로 더해주어야 한다.

 

예를 들어, 동전 1을 이용해서 1~10까지 각각 만들 수 있는 값의 경우는 모두 1이다.

그 다음 동전 2를 이용했을 때, dp[2]에 dp[2 - 2]만큼을 더해주면 dp[2]를 만들 수 있는 경우는 2가 된다.

dp[3]에선 dp[3 - 2]의 경우를 더할테니 동전 1, 2를 같이 쓴 경우를 더해준다.

이런 식으로 로직을 짜주면 간단하게 해결할 수 있는 문제다.

 

---

3. 코드

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

int main(void)
{
    int n, k;
    cin >> n >> k;

    vector<int> info(n);
    vector<int> cache(k+1);

    for (int i=0; i<n; i++)
        cin >> info[i];

    cache[0] = 1;
    for (int i=0; i<n; i++)
        for (int j=info[i]; j <= k; j++)
            cache[j] += cache[j - info[i]];

    cout << cache[k] << endl;
    return 0;
}