BOJ 2294 - 동전 2

동전 2
​ [BOJ] 2294 - 동전 2 ​

기본적인 DP 문제의 하나이다.

Bottom-Up 방식의 DP로 해결 ​

​

​ 코인의 개수 N, 구하려는 가치의 합 K ​

​ 각 가치에 대해 필요한 동전의 개수를 저장하는 배열 dp와 ​

​ 각 동전의 가치를 저장하는 coin이라는 배열을 선언하여 각 동전의 가치를 저장한다. ​

​ dp 배열의 값은 K의 최대값인 10000보다 큰 수 P로 초기화. ​

​

​ dp[0] 을 0으로 초기화 한 후 ​

​ 0~K 까지 ​

​ dp[i]값이 P가 아니라면 ​

​ dp[i + coin[j]] = min (dp[i + coin[j]], dp[i] + 1)

​

​ dp[k]의 값이 P라면 -1 출력 ​ P가 아니라면 dp[k] 출력. ​

​

​ 시간복잡도는 O(NK) 이다. ​


#include <bits/stdc++.h>
using namespace std;

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

int main(void)
{
    scanf("%d %d", &n, &k);
    coin.resize(n);
    for(int i=0;i<10001;i++) dp[i] = 12345678; 
    for(int i=0;i<n;i++)
    {
        scanf("%d", &coin[i]);
    }
    dp[0] = 0;
    for(int i=0;i<k;i++)
    {
        if(dp[i] == 12345678)
            continue;
        for(int j=0;j<n;j++)
        {
            if(i+coin[j] <= k)
            {
                dp[i+coin[j]] = min(dp[i+coin[j]], dp[i]+1);
            }
        }
    }
    if(dp[k] == 12345678)
    {
        printf("-1\n");
        return 0;
    }
    printf("%d\n", dp[k]);
}
Written on June 3, 2019