[개쉬운 풀이] 백준 2293 동전1

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

2293번: 동전 1

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

생각

동전 문제는 전형적인 DP문제이다. x라는 동전이 있다면 이를 이용해 k 원을 만들고 싶으면 k-x원을 만들 수 있는 가짓수와 같다. 왜냐하면 k-x만큼의 방법에서 나는 x라는 동전만 얹으면 되기 때문이다. 이때 k원을 이루는 가짓수를 계산하기 위해서는 k-x를 이루는 가짓수를 알아야 한다. 따라서 우리는 '같은 계산을 반복하지 않게 도와주는 DP'를 이용해야 한다. 따라서 1원부터 k원까지 만들 수 있는 가짓수를 차근차근 dp에 저장하여 최종적으로 dp [k]에 들어가는 값을 찾으면 된다.

 

코드

void sol(){
	//dp를 계산하기 위해 초기값이다.
    dp[0] = 1;
    
    //n가지의 동전별로 생각한다.
    for(int i = 0; i < n; i++){
        int coin = coins[i];
        for(int j = coin; j <= k; j++){
        	//현재 값에 coin값을 뺀 j-coin에 해당하는 가짓수를 더한다.
            dp[j] += dp[j-coin];
        }
    }

    cout << dp[k] << endl;
}

 

전체 코드

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

int n,k;
vector<int> coins;
int dp[10001];

void input(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        coins.push_back(tmp);
    }
}

void sol(){
    dp[0] = 1;
    for(int i = 0; i < n; i++){
        int coin = coins[i];
        for(int j = coin; j <= k; j++){
            dp[j] += dp[j-coin];
        }
    }
    cout << dp[k] << endl;
}

int main(){
    input();
    sol();
    return 0;
}