백준 : 2293, 동전 1

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

정답 비율 : 43.670% (2021.03.01 18:48 기준)

2293번: 동전 1

 

문제 요약 :

N개의 서로 다른 가치의 동전이 주어질 때 이를 조합하여 K를 만드는 모든 경우의 수를 구하시오. 이때 동전의 구성이 같고 순서만 다른 것은 같은 경우로 판단됩니다.

 

 

문제 조건 :

입력 : 첫 줄에는 N(1 ~ 100) , K(1 ~ 10000) 두 개 값이 주어집니다. 그 후 N개의 서로 다른 1 ~ 100000 사이의 값이 주어집니다.

출력 : 모든 경우의 수를 출력합니다. 최대 경우의 수는 unsigned int 범위 안입니다.

시간 : 0.5 초

 

문제 풀이 :

DP를 사용하는 것입니다. 아이디어는 다음과 같습니다.

 

< 우선 설명 전 정의 >

n번째 동전의 가치 : value(n)

동전으로 만들 수 있는 값 : result (최대 K)

result에 대한 경우의 수를 저장한 배열 : DP[result] = 경우의 수

 

설명 : 동전 하나하나를 차례대로 하나씩 차례대로 처리할 때 n번째까지 동전으로 만들 수 있는 모든 result에 대한 경우의 수를 알고 있을 경우 n + 1 번째 동전 포함하여 만들 수 있는 모든 값(K보다 작거나 같은)에 대한 경우의 수는 다음과 같습니다. 

 

result에 대하여 bottom-up 방식 : 1 -> K

DP[0] = 1

DP[result] = DP[result] + DP[result - value(n)] ( result >= value(n) )

DP[result] = DP[result]  ( result < value(n) )

 

result에 대하여 top-down 방식 : K -> 1

DP[result] = DP[result] + 1 ( result % value(n) = 0 )

DP[result] = DP[result] + DP[result - value(n) * 1] + ... + DP[result - value(n) * t] ( result - value(n) * t >= 0 )

 

위 점화식에서 알 수 있듯이 result에 대하여 bottom-up 방식이 더욱 효율 적입니다.

 

코드는 다음과 같습니다.

 

C99 (top-down)

#include<stdio.h>

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

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++)
	{
		int value = K + 1;
		
		while(--value)
		{
			DP[value] = DP[value] + (value % coin[i] ? 0 : 1);
			
			for(j = 1; j <= value / coin[i]; j++)
				DP[value] = DP[value] + DP[value - coin[i] * j];
		}
	}
	
	printf("%d\n", DP[K]);
	
	return 0;
}

 

 

C99 (bottom-up)

#include<stdio.h>

int DP[10001] = {1, };
int coin[100];

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++)
	{
		for(j = 1; j <= K; j++)
			DP[j] = DP[j] + (j >= coin[i] ? DP[j - coin[i]] : 0);
	}
	
	printf("%d\n", DP[K]);
	
	return 0;
}