BOJ 2293 - 동전 1
알고리즘/동적 계획법문제
풀이
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;
}