[BOJ] 2294번_동전 2_DP (C++)

[문제]

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

N과 K를 입력받은 후 N개의 종류의 동전을 입력받는다. 그리고 입력받은 동전들을 적당히 조합해서 합을 K원으로 만드는 문제이다.

[사용 알고리즘]

DP(다이나믹 프로그래밍)

[풀이 핵심]

• 문제의 예시로 생각해보자.

1. 먼저 최소값을 구해야하기 때문에 dp의 0번째 인덱스 값을 제외한 모든 값을 99999으로 초기화한다.

2. 이제 1원을 사용해서 1원을 만든다고 생각하면, dp[1]과 dp[1-1]+1 중에서 최소 값을 골라주면된다. dp[1-1]+1은 1원에서 1원을 빼고 1원짜리 동전을 한개 추가해준다. 라는 뜻이다.
   2원을 만든다고 생각하면, 마찬가지로 dp[2]와 dp[2-1]+1 중에서 최소 값을 골라주면된다. dp[2-1]+1은 당연히 2원에서 1원을 빼고 1원짜리 동전을 한개 추가해준다. 라는 뜻이다.
   이런식으로 1원부터 K원까지 만들어주면된다.

3. 다음으로 5원을 사용해서 5원을 만든다고 생각해보자. 5원으로 1~4원은 만들 수 없으므로 5원부터 만들어보면, dp[5]와 dp[5-5]+1 중에서 최소값을 고르면된다. dp[5]는 2번 풀이에서 1원 5개로 5원 만들기를 진행했으므로 5가 들어있다. 따라서 dp[5-5]+1을 골라주면 된다.
   이것도 마찬가지로 5원부터 K원까지 만들어주면된다.

4. 마지막으로 12원을 사용해서 12원을 만들어보자. 12원도 1~11원은 만들 수 없으므로 12원부터 만들어보면, dp[12]와 dp[12-12]+1 중에서 최소값을 고르면 된다. dp[12]는 풀이 2번에서 12의 값을 가지고 있다가 풀이 3번에서 4의 값으로 바꼈다. 따라서 dp[12-12]+1을 골라주면 된다.
   이것도 마찬가지로 12원부터 K원까지 만들어주면된다.

5. 위의 예제를 통해 점화식은 dp[동전의 가치] = min(dp[동전의 가치], dp[동전의 가치 - 현재 사용하려는 동전] + 1(동전 한개 추가)) 라는 것을 알 수 있다.

[코드]

//boj2294번_동전 2_dp

#include<iostream>
#include<vector>

using namespace std;

int dp[10001];

int main() {
	int N, K;
	cin >> N >> K;

	vector<int> v;

	v.push_back(0);

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	for (int i = 1; i <= K; i++) {
		dp[i] = 99999;
	}
	
	for (int i = 1; i <= N; i++) {
		for (int j = v[i]; j <= K; j++) {
			dp[j] = min(dp[j], dp[j - v[i]] + 1);
		}
	}

	if (dp[K] == 99999) {
		cout << -1;
	}
	else {
		cout << dp[K];
	}

	return 0;
}