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

동전 2

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음)128 MB55849167351176729.214%

문제

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

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

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

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

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

입력

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

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

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

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

출력

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

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

예제 입력 1

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
3 15
1
5
12
3 15 1 5 12
3 15
1
5
12

예제 출력 1

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
3
3
3

출처

알고리즘 분류


문제 정리

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) 찾는 것

통과된 코드

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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 문제를 풀면 풀수록 점점 아리송해진다…

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다