동전 2

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	128 MB	55849	16735	11767	29.214%

문제

n가지 종류의 동전이 있다.

이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

그러면서 동전의 개수가 최소가 되도록 하려고 한다.

각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)

다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 

동전의 가치는 100,000보다 작거나 같은 자연수이다.

가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다.

불가능한 경우에는 -1을 출력한다.

예제 입력 1

3 15
1
5
12

예제 출력 1

3

출처

• 잘못된 조건을 찾은 사람: apples1309, djm03178
• 빠진 조건을 찾은 사람: goodcrane3
• 데이터를 추가한 사람: hayman42, isac322, paraworld

알고리즘 분류

• 다이나믹 프로그래밍

---

문제 정리

N개의 동전과 가치 K가 주어진다. (1 <= N <= 100), 1 ≤ K ≤ 10,000)

동전은 각각 가치를 가지고 있고, 동전이 다르더라도 가치가 같을 수 있다. ( 1<= v <= 100,000)

주어진 동전들을 조합하여(동전을 중복으로 사용 가능) 가치의 합이 K가 되는 최소 동전의 수를 구한다.

만약 합을 K로 만들 수 없다면 -1을 출력한다.

목표 가치로 접근

문제의 포인트는 F[K] = Min(F[K] , F[K – X] + 1) 찾는 것

통과된 코드

#include <iostream>
#include <algorithm>

using namespace std;

// 코인의 가치 범위 1 ~ 100   
// 배열의 범위 coin[0 ~ 100]
// coin[N] = N번째 코인의 가치를 나타낸다.
int coinValue[101]; // 예제 {1, 2, 15, 0, 0 ....}

// 주어지는 목표 가치의 범위 1 ~ 10,000   
// 배열의 범위 [0 ~ 10,000]
// TargetValue[K] = K가치를 만드는 동전의 최소 개수
int TargetValue[10001];

// N 동전의 수, K 목표 가치
int N, K;

// 문제를 초기화 해주는 기능의 함수
void Initialization()
{
	// 동전의 수, 목표 가치를 입력받음
	cin >> N >> K;
	
	// 동전의 순서대로 가치를 입력받음
	// 인덱스틑 1번부터
	int temp = 1;
	while (temp <= N) {
		cin >> coinValue[temp];
		temp++;
	}

	for (int i = 0; i <= K; i++) {
		// 목표 가치가 0인 경우 필요한 동전의 수는 0개 
		// 점화식을 전개할때 필요하다.
		if (i == 0) { 
			TargetValue[i] = 0; 
			continue;
		}

		// 동전의 최소 가치는 1
		// 주어지는 목표의 가치의 최대값은 10,000
		// 동전의 개수가 10,000개를 넘어가는 경우는 없다.
		// 문제에서 불가능한 경우를 -1로 출력할때 필요
		TargetValue[i] = 10001;
	}

}

int main()
{
	Initialization(); // 문제 조건을 조기화

	// 입력받은 동전의 개수만큼 순회
	for (int i = 1; i <= N; i++) {
		// 입력받은 목표 가치까지 순회
		for (int j = 1; j <= K; j++) {
			
			// 코인의 가치 > 목표의 가치 넘어간다.
			// TargetValue[K]가 변하지 않는다.
			if (coinValue[i] > j) { continue; }

			// TargetValue[K - coinValue[N] + 1] 
			// 목표 가치에서 현재 순서의 코인의 가치를 한번 뺀다면 해당 코인을 1개 추가한 것과 같다.
			// 기존의 TargetValue[K]와 비교하여 더 작은 수를 넣는다.
			TargetValue[j] = min(TargetValue[j], TargetValue[j - coinValue[i]] + 1);
		}

	}

	// 목표 가치의 동전의 개수가 범위에서 벗어나는 수라면
	// 동전으로 목표의 가치를 만들 수 없다는 뜻 => -1을 출력
	if (TargetValue[K] >= 10001) { cout << -1; }
	else { cout << TargetValue[K]; }

	return 0;
}

DP 문제를 풀면 풀수록 점점 아리송해진다…