[백준 2294번] 동전 2 (C++)

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

2294번: 동전 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K;
int arr[101];
int dp[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K;
    for(int i=0; i<N; i++) cin >> arr[i];
    fill(dp, dp+1000001, MAX);
    for(int i=0; i<N; i++) dp[arr[i]]=1; //초기화
    for(int i=0; i<N; i++)
    {
        for(int j=arr[i]; j<=K; j++)
        {
            dp[j] = min(dp[j], dp[j-arr[i]]+1); //점화식
        }
    }
    cout << (dp[K] == MAX ? -1 : dp[K]);
    return 0;
}

백준 2293번 동전 1 문제와 유사한 문제이다.

동전 1의 경우에는 모든 경우의 수를 구하는 것이었고, 동전 2의 경우는 동전의 최소 사용 갯수만 구하는 것이다.

 

처음에 초기값을 설정해주는데 dp[arr[i]]=1을 해줌으로써 입력받은 동전들에 대해서 최소 갯수인 1로 초기화해준다.

그리고 최소값을 넣어주는 DP 배열도 MAX로 초기화해주었다.

 

이 후 이를 토대로 현재 합에 대해 동전들이 이루는 경우의 수의 최소값을 담아주는데 현재 값과 현재 동전을 사용하기 이전 값 + 1을 비교하여 최소값을 담아준다.

(ex : K=5 -> 5원 동전 1개 vs 1원 동전 5개)

 

그리고 출력시에 주어진 동전의 합으로 K를 만들기가 불가능하다면 -1을 출력해주어야한다.