백준 2293 동전 1 풀이

목표: 백준 2293 동전 1 풀이

환경: mac OS Mojave 10.14, CLion

로직

문제이해

DP 문제이고, 동전 시리즈 중 한 문제입니다. 작은 문제로 큰 문제를 풀 수 있을 것이란 생각을 통해 DP로 접근하였고, 역시나 DP였음.

문제접근

동전의 가치가 주어지고, 주어진 동전을 이용해서 가치의 합이 k가 되는 경우의 수를 구하라.
DP의 문제는 겹치는 작은 문제와 한번 구한 답을 이용해라. 이 두 가지를 풀이하면 되는데
dp[i]라는 배열을 선언했고, 그 의미는 합이 i가 되는 경우의 수를 구하라. 그러면 topdown 방식으로 알고리즘이 생각이 났고, 코드는 bottom up으로 구현했음.

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int main() {

    map<int,int> dp;
    vector<int> data;
    int n,k,inputData;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> inputData;
        data.push_back(inputData);
    }

    dp[0] = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if( j-data[i] >=0)
                dp[j] += dp[j - data[i]];
        }
    }

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