백준 : 2294, 동전 2

문제 주소 : www.acmicpc.net/problem/2294

정답 비율 : 28.169% (2021.03.03 22:47 기준)

2294번: 동전 2

 

문제 요약 :

newbie22.tistory.com/158

백준 : 2293, 동전 1

동전 1 문제와 아주 유사합니다. 다른 점은 출력하는 것은 최소로 사용하는 동전의 개수이며 이때 각 동전의 가치가 중복으로 주저질 수 있습니다.

 

문제 조건 :

입력 : 첫 줄에는 N(1 ~ 100) , K(1 ~ 10000) 두 개 값이 주어집니다. 그 후 N개의 1 ~ 100000 사이의 값이 주어집니다. 동전의 값어치에 대하여 중복 값이 존재할 수 있습니다.

출력 : 동전의 최소 개수를 출력합니다. 이때 불가능 경우에는 -1을 출력합니다.

시간 : 1 초

 

문제 풀이 :

이 또한 DP 문제입니다. 아이디어는 다음과 같습니다.

 

1. 우선 N개의 동전을 한 개씩에 데이터를 구축합니다.

2. DP에는 1 ~ K 만들 수 있는 경우 중 가장 적게 드는 경우를 저장합니다. 이때의 데이터는 1 ~ n 번째 동전을 사용한 경우입니다.

3. 동전으로 k 값(1 ~ K)을 만들기 위하여 해당 동전(n, 가치 : v)이 최대로 들어갈 수 있는 개수(T)를 구합니다.

4. DP[k - v * t] + t (t : 1 ~ T) 중 DP[k - v * t]가 0이 아닌 최솟값을 구합니다. (DP[k - v * t]가 0이 아닌 이유는 해당 값이 0이면 이는 1 ~ n - 1까지 동전을 사용하여 k - v * t 인 경우가 존재하지 않음을 의미하기 때문입니다.)

5. 해당 최솟값과 DP[k]를 비교하여 더 작은 값을 구합니다. (단, DP[k]가 0이 아닌 경우, DP[k]가 0이면 위에서 구한 최솟 값이 DP[k] 값이 되겠습니다.)

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int DP[10001] = {0, };
int coin[100];
int visit[100000] = {0, };

int min(int a, int b)
{
	if(a == 0) return b;
	else if(b == 0) return a;
	else if(a > b) return b;
	else return a;
}

int main()
{
	int N, K, i = -1, j = -1;

	scanf("%d %d", &N, &K);
	
	for(i = 0; i < N; i++)
		scanf("%d", &coin[i]);
		
	for(i = 0; i < N; i++)
	{
		if(visit[coin[i] - 1]++ == 0)
		{
			for(j = 1; j <= K; j++)
			{
				int multi = j / coin[i], z = -1;
				
				for(z = multi; z > 0; z--)
				{
					if(j - z * coin[i] == 0 || DP[j - z * coin[i]] != 0)
						DP[j] = min(DP[j], DP[j - z * coin[i]] + z);
				}	
			}
		}
	}
	
	printf("%d\n", (DP[K] ? DP[K] : -1));
	
	return 0;
}

-> 이때 visit을 사용하는 이유는 중복 값이 주어지기 때문입니다.

 

하지만 해당 방법을 보면 K값에 대하여 botton-up방식으로 DP를 구성하지만 실질적으로 DP값을 구축하는 데 있어서 multi 값을 사용하여 top-down 방식을 사용하는 것을 확인할 수 있습니다.

 

좀 더 효율적인 방법이 있습니다. 이는 DP[k]에 K + 1의 값을 저장하는 것입니다. 그리고 조사 조건을 

coin의 value >= k이고 DP[k] > DP[k - coin의 value]를 만족하면 됩니다. 

 

해당 방식을 사용하면 DP[k - coin의 value]가 1 ~ n번째 coin을 사용하여 만들 수 없는 값이면 최대 값인 K + 1 인 값이 저장되고 이는 DP[k] 값이 K + 1 보다 클 수 없기 때문입니다.

 

이때 해당 실행에서 DP의 최댓값이 K + 1인 이유는 coin의 최솟값이 1이고 1을 이용하여 DP[K]를 구축하면 DP[K]의 최솟값은 K이기 때문입니다. 

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int DP[10001] = {0, };
int coin[100];
int visit[100000] = {0, };

int main()
{
	int N, K, i = -1, j = -1;

	scanf("%d %d", &N, &K);
	
	for(i = 0; i < N; i++)
		scanf("%d", &coin[i]);
	
	for(i = 1; i <= K; i++)
		DP[i] = K + 1;
		
	for(i = 0; i < N; i++)
	{
		if(visit[coin[i] - 1]++ == 0)
		{
			for(j = 1; j <= K; j++)
			{
				if(j >= coin[i] && DP[j] > DP[j - coin[i]])
					DP[j] = DP[j - coin[i]] + 1;	
			}
		}
	}
	
	printf("%d\n", (DP[K] != K + 1 ? DP[K] : -1));
	
	return 0;
}

 

 

***

동전 1과 동전 2 문제를 풀면서 아직 DP문제에서 뭐를 DP 구축해야 할지는 감을 잡았지만 아직 효율적인 DP구축에 대하여 부족함을 느꼈습니다.