백준 2293 / 동전 1

다이나믹 프로그래밍 문제

풀이법은 1,2,3 더하기 4 문제와 같다. (https://naivep.tistory.com/66)

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우라는 뜻은 중복을 허용하지 않는다는 뜻.

d[i]가 i원을 만들 수 있는 경우의수라고 하면

모든 동전마다 그 동전으로 i원을 만들 수 있는 경우의 수를 d[i]에 추가해준다.

그렇기 때문에 for문의 순서는

for(동전의 개수)

for(0부터 k까지)

가 되고,

중복이 허용되는 경우는

for(0부터 k까지)

for(동전의 개수)

로 하면 된다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<memory.h>
 
using namespace std;
 
int coin[101];
int d[10001];
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
    int n, k;
 
    cin >> n >> k; 
 
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
        
    }
 
    d[0] = 1;
    
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= k; i++) {
            int cost = coin[j];
 
            if (i - cost >= 0) {
                d[i] += d[i - cost];
            }
        }
    }
 
    cout << d[k];
}