[백준] C++ 알고리즘 2294번 - 동전2문제

문제

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

2294번: 동전 2

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <stdio.h>
using namespace std;
int dp[10001];
int arr[101];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= k; i++) dp[i] = 10001;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			if (arr[i] <= j) {
				dp[j] = min(dp[j], dp[j - arr[i]] + 1);
			}
		}
	}
	if (dp[k] == 10001) cout << "-1";
	else cout << dp[k];
}

해설

매번 K번째 동전을 계산하기 위해 모든 경우의 수를 다 살펴볼 순 없으니 DP를 이용하여 점화식을 세워보자.

우선 i번째까지 동전으로 j원을 만들 때 동전의 최소개수를 구하는게 문제의 요지이다.

제일 처음 1원짜리는 이전의 초기값이 없으니 1원짜리로 만들 수 있는 동전의 수를 저장시킵니다.

그다음 5원까지 사용할 수 있을 때의 최소 동전개수를 생각해야합니다.

5원이하의 동전인 j는 5원으로 만들 수 없으니 그대로 1원짜리로 만들 수 있는 경우만 가져갑니다.

5원이 되었을 때 경우를 따져봐야합니다.

5원 한개만 쓸 것인가 아니면 1원5개로 5원을 만들 것인가

즉 dp[j] = min(dp[j], dp[j-arr[i]]+1) 로 점화식을 작성할 수 있습니다.

 

dp[j-arr[i]]의 의미를 잘모르겠다면

j원을 만들기 위해 코인arr[i]에 있는 것을 빼게된다면 그 이전에 arr[i] 코인까지 만들 수 있는 동전의 최소개수가 들어가져있으니, 이 값에서 +1을 하게되면 j원을 만드는데 필요로한 동전의 개수를 저장할 수 있다.