백준, boj) 2624. 동전 바꿔주기

1. 문제 링크

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

2624번: 동전 바꿔주기

2. 문제 개요

지폐의 금액과 동전의 가짓수, 금액과 개수가 주어질 때, 지폐의 금액인 T를 바꿔줄 수 있는 가짓수를 출력하자.

 

3. 문제 힌트

 완전탐색인데 DP 메모이제이션을 사용.

 

4. 문제 풀이

 

모든 동전에 대하여, 안쓸경우 1개만 쓸 경우 2개만 쓸 경우.... n_i개만큼 쓸 경우를 비교한다.

과정은 메모이제이션을 통하여 시간 복잡도를 줄인다.

 

문제의 보기를 예로 들어보자, dp(cash,0)은 cash원을 0번째 동전부터 시작하여 바꿀 수 있는 가짓수를 나타내는 함수라고 하자.

 

dp(20,0)이다.

현재는 20원이고 0번째 동전을 사용할건데 문제에서 0번째 동전은 5원짜리 3개이다.

5원을 안쓰고, 1번째 동전으로 간다.

1번째 동전도 안 쓴다. 2번째 동전으로 간다.

2번째 동전은 1원이다. 1원도 안 쓴다.

3번째 동전은 없다. 조건을 만족하지 않고 (안 씀, 안 씀, 안 씀) 이 경로는 답이 될 수 없다. 0 반환. ( 기저 조건이 됨 )

그러면 2번째로 돌아와서 1원을 1개 써보자, 그리고 3번째 동전으로 간다.

3번째 동전은 없다. 이것 또한 조건을 만족하지 않는다. (안 씀, 안 씀,1원 : 1개) 이 경로도 답이 될 수 없다. 0 반환.

이렇게 진행하다가

(5원 1개, 10원 1개, 1원 5개)가 되는 경우가 있을 것이다. 이 경로는 조건에 만족하므로 1을 반환해서 값을 누적시켜주자.(기저 조건)

 

위와 같은 알고리즘이다.

결국엔 완전 탐색이다. 이것을 메모이제이션 해주면 시간을 단축시킬 수 있다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int t, k;

//first 가치, second 갯수
pair<int, int> v[101];
int dp_table[10001][101]; //두번째 index는 사용한 동전 종류의 개수를 나타내기위함.

int dp(int cash, int cur)
{
	if (cash == 0)
		return 1;	//돈을 딱 맞게 바꿀 수 있는 경우
	if (cur >= k)
		return 0;	//다 써도 돈을 딱 맞게 바꿀 수 없는 경우

	int &cache = dp_table[cash][cur];
	if (cache != -1)	return cache;

	int ans = 0;

	for (int i = 0; i <= v[cur].second; ++i)
		if (cash - v[cur].first *i >= 0)
			ans += dp(cash - v[cur].first*i, cur + 1);

	return dp_table[cash][cur] = ans;
}


int main()
{
	scanf("%d", &t);
	scanf("%d", &k);
	memset(dp_table, -1, sizeof(dp_table));

	for (int i = 0; i < k; ++i)
		scanf("%d %d", &v[i].first, &v[i].second);

	printf("%d", dp(t, 0));
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~