백준 2293 동전

문제

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

풀이전략

1. 문제에 input, output을 먼저 분석하고 풀어야한다.
2. 이전에 카드구매하기, 다리놓기문제와 알고리즘이 비슷하다. 예를들어 가치의 합이 10원이 되도록 해야하면 모든 종류의 동전들을 검사하여 더해주어야한다.

코드

#include<bits/stdc++.h>

using namespace std;



int main(){
    ios_base::sync_with_stdio(false);
    freopen("../input.txt","rt",stdin);
    
    int i, j, n, k;
    int dp[10001] = {0,};

    cin >> n >> k;

    int coins[n];

    for(i=0; i<n; i++) scanf("%d",&coins[i]);
    dp[0] = 1;

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

    return 0;
}

소감

해결하지 못하여 다른분의 코드를 보았다. 이 문제를 보고 다리놓기, 카드구매하기 문제도 다시한번 복습해야겠다.