백준 2293번 : 동전 1

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

2293번: 동전 1

 

 

 문제 설명 

 

1. 첫 줄에 n,k 가 주어짐.

2. n은 동전의 갯수이고 k는 맞춰야 하는 금액

3. 그다음 n개의줄에 동전의 가치가 주어지고 가지고있는 동전들로 만들수있는 k의 경우의 수 출력.

 

 알고리즘 

 

1. 먼저 표를 만들어서 점화식을 유추 

2. 점화식 : dp[i]= dp[i-coin[j]]+dp[i];

3. 점화식을 이용하면 쉽게 풀린다 .

 

 코드 

 

#include<iostream>
#include<algorithm>
using namespace std;
int coin[101];
int dp[10001];
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    int n, k;
    cin >> n >> k;
 
    //동전 입력
    for (int i = 0; i < n; i++) {
        cin >> coin[i];
    }
 
    //오름차순 정렬
    sort(coin, coin + n);
    
    //dp 초기화
    dp[0] = 1;
    for (int i = 1; i <= k; i++) {
        dp[i] = 0;
    }
 
    for (int i = 1; i <= k; i++) {
        //첫번째 코인 이용
        if (i % coin[0] == 0)dp[i] = 1;
    }
    for (int j = 1; j < n; j++) {
        //나머지 코인 이용 
        for (int i = coin[j]; i <= k; i++) {
            dp[i] = dp[i - coin[j]] + dp[i];
        }
    }
    cout << dp[k];
}