[백준] 2293번 동전1

문제 링크: https://www.acmicpc.net/problem/2293

문제 및 입출력

문제 접근

dp문제이다. 이 문제는 조금만 생각하면 나름 단순한 문제였다. 만들어야되는 가치(원)을 dp 배열에 저장해두고 사용했다. 먼저 0원이라는 동전이 있다고 가정하고, 0가치부터 하였다. 그래서 dp[0] = 1이였고, 동전 하나씩을 계산하였다. 현재 가치는 현재 가치에 저장되어 있는 값과 그 가치에서 현재 동전의 가치를 빼서 얻을 수 있다.
dp[i] = dp[i] + dp[i-coin[cur]]

코드 구현(c++)

#include <iostream>
#include <cstring>

using namespace std;
int dp[10001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    int n,k;
    cin >> n >> k;
    int coin[n];
    for(int i = 0 ; i < n ; i++){
        cin >> coin[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for(int i = 0 ; i < n ; i++){
        for(int j = coin[i] ; j <= k ; j++){
            dp[j] = dp[j] + dp[j-coin[i]];
        }
    }
    cout << dp[k] << "\n";

}