(c++) 동적계획법 BOJ 2293번: 동전 1

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

2293번: 동전 1

 

 

 

 

문제 개요

 

 

 

주어진 K에 대해서 동전 조합으로 만들 수 있는 경우의 수를 계산하는 코드이다.

 

동전 조합이 1, 2가 있다면

 

동전 1를 이용해서 만들 수 있는 조합은

1 = (1)   1가지

2 = (1, 1) 1가지 

3 = (1, 1, 1) 1가지

 

동전 2를 이용해서 만들 수 있는 조합은

1 = 없음

2 = (2) 1가지

3 =  1원을 사용해서 (2, 1)만 가능

여기서 3은 3에서 2를 뺀 1원을 동전 1로 만들 수 있기에 

여기서 3원의 경우의 수는

3 - 2 = 1원을 만드는 경우의 수와 같다.

 

이 아이디어를 이용해서 코드를 짜보면 아래와 같다.

sum[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = coin[i]; j <= k; j++) {
        sum[j] = sum[j] + sum[j - coin[i]];
    }
}

 

 

ex)

k = 5 이고 동전 종류는 1, 2라고 생각해본다면

 

n이 0 즉 동전 종류 1이라면

 

1, 2, 3, 4, 5 = {1, 1, 1, 1, 1} 이 되고,

 

n = 1 즉 동전 종류 2라면

 

1, 2, 3, 4, 5 = {1, 2, 2, 3, 3} 이 되며 중복되지 않고 결과값이 제대로 나올 수 있다.

 

여기서 이중 반복문 부분을 coin[i]로 시작하는 것은 동전보다 작은 배열은 음수가 나오기 때문이다.

 

 

 

 

 

코드

 

 

 

 

#include <bits/stdc++.h>

using namespace std;
int n, k;
int coin[100], sum[10001];

int coin_n() {
    sum[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coin[i]; j <= k; j++) {
            sum[j] = sum[j] + sum[j - coin[i]];
        }
    }
    return sum[k];
}

int main(void) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }
    cout << coin_n();
}