백준 2293번: 동전 1

 

https://www.acmicpc.net/problem/2293

 

 

1. 문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)

 

2. 알고리즘

키워드 - 다이나믹 프로그래밍 

 

https://www.youtube.com/watch?v=2IkdAk1Loek

 

백준 2293번 동전 1.pptx

0.06MB

 

 

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


#include <iostream>
#include <algorithm> // min
#include <functional>
#include <math.h>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <sstream>
#define MAX_SIZE 100
int coin[MAX_SIZE];
int dp[10001];

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0);

    int n, k; cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }

    dp[0] = 1;
    // n 동전의 갯수
    for (int i = 0; i < n; i++) {
        // k = n 개의 동전으로 만들 수 있는 총 합
        for (int j = coin[i]; j <= k; j++) {
            dp[j] += dp[j - coin[i]];
        }
    }

    cout << dp[k] << "\n";
    return 0;
}