BOJ 2293 - 동전 1

문제

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

풀이

Coin Change라는 이름으로 유명한 DP 문제이다. 이 문제는 2차원 배열을 사용해서 해결할수도 있고 1차원 배열을 사용해서 해결할수도 있는데 2차원 배열 사용하면 6MB 정도의 메모리를 사용하게 되므로 문제의 메모리 제한을 초과하게 된다. 

일단 2차원 풀이법부터 설명해보자면, dp[n][k] = n 종류의 동전으로 k원을 만드는 경우의 수라고 정의할때 dp[n][k]를 구하는 방법은 두가지이다.

1. dp[n][k-coin[n]] = n번째 동전을 사용한 뒤 k원을 만들수 있는 경우의 수

2. dp[n-1][k] = n번째 동전을 사용하지 않고 k원을 만들수 있는 경우의 수

이렇게 되므로 점화식은 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $가 된다.

#include<stdio.h>
#include<string.h>
int coin[100]={0},cache[100][10001];
int solve(int n,int k){
	if(n<0||k<0)return 0;
	if(k==0) return 1;
	if(cache[n][k] != -1) return cache[n][k];
	return cache[n][k] = solve(n,k-coin[n]) + solve(n-1,k);
	
}
int main() {
	int n,k,i;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++){
		memset(cache[i],-1,sizeof(cache[i]));
		scanf("%d",&coin[i]);
	}
	printf("%d",solve(n-1,k));
}

물론 위는 2차원 배열을 사용해서 메모리 초과가 발생한다. 1차원 풀이는 아무리 생각해도 모르겠어서 여러 문서를 뒤져보고 이해했다.

2차원 배열을 사용하는 점화식이 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $인데, 여기서 n이 1증가하면 결국은 $ dp[n][k] = dp[n][k-coin[n]] $이되므로 $ \sum\limits_{i=coin[n]}^k cache[i] = cache[i] + cache[i - coin[n]] $이 된다.

#include <stdio.h>
int main(void) {
	int i,j,n,k,coin[100]={0},cache[10001]={0};
	scanf("%d%d",&n,&k);
	cache[0]=1;
	for(i=0;i<n;i++){
		scanf("%d",&coin[i]);
		for(j=coin[i];j<=k;j++)
			cache[j] += cache[j-coin[i]];
	}
	printf("%d",cache[k]);
	return 0;
}