백준 2294 - 동전 2

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

2294번: 동전 2

n가지 종류의 동전이 있습니다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶은데 그러면서 동전의 개수가 최소가 되도록 하려고 합니다.( 각각의 동전은 몇 개라도 사용할 수 있다. )

이때 동전의 최소 갯수를 구하는 문제입니다.

저는 다이나믹 프로그래밍의 방법으로 접근했습니다.

 

1원부터 시작해서 원하는 값까지 계속 최솟값을 비교해가는 방식을 사용했습니다. 

 

1. 동전 갯수의 최솟값을 구하기 위해서 모든 배열의 값에 큰 값을 입력하고 시작한다.

2. 가지고 있는 동전의 값에서는 만들 수 있는 경우가 1가지 임으로 모두 1을 대입합니다.

    - 3원 동전을 가지고 있다면 3원을 만들 수 있는 최소 방법은 1가지이다.

3. 동전의 최솟값전까지는 만들 수 있는 방법이 없음으로 -1을 대입한다.

4. 동전의 최솟값부터 만들고 싶은 값까지 for문을 통해서 구한다.

    - number[i] = min(number[i - coin[j]] + 1, number[i]); -> 점화식입니다

 

제가 구현한 점화식에 대해서 설명하겠습니다.

일단 동전의 최소 가치부터 구하고자하는 값까지 for문을 반복했습니다.

 -> 값이 하나씩 증가하면서 해당 단계의 동전의 최소 개수를 구한다음 이용할 것입니다.

각 단계에서 구하고 싶은 값을 알기 위해서는 가지고 있는 동전의 가치를 뺀다음 1을 더하는 것입니다. 

예를 들자면 15원을 만들고 싶은데 가지고 있는 동전은 1원, 5원, 12원 입니다

그렇다면 14원까지의 최소 갯수 + 1,

            10원까지의 최소 갯수 + 1,

             3원까지의 최소 갯수 + 1  의 경우의 수가 나옵니다.

이 3가지의 경우의 수를 비교해 가장 작은 수를 가져온다면 구하고자하는 최소 갯수가 됩니다.

밑의 코드를 보시면 자세한 것은 이해가 될 것입니다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>

using namespace std;

int number[10000001];
int number_coin;
int want_make;
int coin[100001];
int min_coin = 10000001;

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> number_coin >> want_make;	
	for (int i = 1; i <= want_make; i++) {
		number[i] = 100000001;
		//만들 수 있는 최솟값을 비교하기 위해 큰수를 집어넣는다.
	}
	for (int i = 1; i <= number_coin; i++) {
		cin >> coin[i];
		number[coin[i]] = 1;
		min_coin = min(min_coin, coin[i]);
		//코인의 최솟값 구하기
	}
	for (int i = 1; i < min_coin; i++) {
		number[i] = -1;
		//최솟값전까지는 만들 수 없음으로 -1 넣어준다.
	}
	for (int i = min_coin; i <= want_make; i++) {
		if (number[i] != 1) {
			for (int j = 1; j <= number_coin; j++) {
				if (i - coin[j] > 0) {
					if (number[i - coin[j]] > 0) {
						number[i] = min(number[i - coin[j]] + 1, number[i]);
					}
				}
			}
		}
		//cout << number[i] << " " << i << "\n";
	}
	if (number[want_make] == 100000001) cout << "-1";
	else cout << number[want_make];
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!