C++ / 2294 / 동전 2 ( 다이나믹 프로그래밍 )

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

문제 요약

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

그러면서 동전의 개수가 최소가 되도록 하려고 합니다. 각각의 동전은 몇개라도 사용할 수 있습니다.

 

동전 1 : https://lgj415415.tistory.com/58

 

이 문제는 지난 동전 1과 이어지는 문제입니다. 동전 1은 x원 짜리 동전이 금액 마다 몇개씩 들어갈수있는지 총합이었다면동전 2는 금액을 만들 수 있는 최소한의 동전 갯수를 구해야 한다는 것입니다.

문제 풀이

1. 동전 종류의 개수와 계산하고 싶은 값을 입력받습니다.

2. dp 함수를 만드는데, 먼저 0번째는 0을 넣고 ( 0은 결과가 0이기 때문 ) 1e9( 1에 10의 9제곱을 곱한 값 )로 경우의 수를 넣을 배열을 초기화 하여 줍니다. 

초기화를 해주는 이유는 후에 더 작은 경우의 수를 갱신하여 줄려 하는데 초기화를 하지 않은 배열에선 첫번째 반복문을 돌 경우에 비교할 대상이 없기 때문입니다.

3. 동전의 종류 만큼 반복문을 하고 그 안에서 동전의 값어치 부터 계산하고 싶은 값 까지 반복문을 돌립니다. ( 경우의 수 초기화 )

 

4. 규칙

(현재 숫자 - 동전의 값어치) 의 경우의 수에 + 1을 해주면 현재 숫자의 최소한의 경우의 수를 구할 수 있습니다. 

구하려는 금액이 최소 동전의 값어치보다 작은 경우라면 동전의 값어치부터 계산을 시작하기 때문에 접근 조차 할 수 없습니다.

따라서 위에 초기화한 1e9값이 들어있게 됩니다.

만약 가지고 있는 동전들로 만들 수 없는 값이면 (현재 숫자 - 동전의 값어치)의 경우의 수가 1e9가 들어있고 거기에 +1을 하더라도 1e9보다 커기지 때문에 갱신이 되지 않습니다.

 

5. 새로운 경우의 수가 기본 경우의 수 보다 작을경우에 갱신하여 줍니다.

6. 출력할때 원하는 숫자의 경우의 수가 1e9 ( 갱신이 되지 않음 ) 이면 -1을 출력하고 아닐 경우에 경우의 수를 출력합니다. 

주의할 점

이 문제도 저번 동전 1과 마찬가지로 생각보다 시간이 걸렸습니다.

먼저 배열을 무한대 or 1e9로 초기화하는 것이 중요합니다.

첫 번째 돌때 비교할  대상이 필요하기 때문입니다.

또한 p[ j - v[ i ] ] + 1 현재 동전의 값어치( v[ i ] )로 만들 수 있는 경우의 수 라는 걸 눈치 채야 합니다.

코드

#include<iostream>
#include<vector>


using namespace std;

int n, k;
int p[100004];
vector<int>v;


void dp()
{
	p[0] = 0;

	// 비교를 위해 배열 초기화
	for (int i = 1; i <= k; i++)
	{
		p[i] = 1e9;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = v[i]; j<= k; j++)
		{
			// 기존 경우의 수가 새로운 경우의 수 보다 클경우
			if (p[j] >= (p[j-v[i]] + 1))
			{
				// 갱신
				p[j] = (p[j-v[i]] + 1);
			}
		}
	}
}

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back(a);
	}


	dp();

	// 갱신 되지 않았을경우 -1
	if (p[k] == 1e9)
	{
		cout << -1;
	}
	else
	{
		cout << p[k];
	}


	return 0;
}

반응형

예제

3 15
1
5
12

결과