문제

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

풀이

주어진 N을 가지고 사면체를 최소로 만들어 N을 0으로 만드는것이 목표이다. 다르게 말하자면 그냥 동전 교환 문제이다.

만약 항상 한 개의 사면체를 만들만큼만 N이 주어진다면 좋겠지만 탐욕법으로 풀 수 있겠지만 동전 1문제 처럼 이 문제는 탐욕적으로 풀 수 없는 케이스가 있다.

예를들어 N이 50일때 탐욕법을 이용해 풀면 $45+3+1+1$가 답이되어 4개가 답이 되지만 실제로는 $20+20+10$로 3개가 최소이다.

동전 문제와는 다르게 이 문제는 사면체 수가 주어지지 않는데 이 값들은 여러번 사용할 것이므로 사면체 수를 구해놓고 배열에 저장해놓는다면 시간을 매우매우 줄일수 있다.

만약 입력값이 작다면 그냥 풀어도 되지만 문제 최대 입력이 300,000이고 이 값이 들어왔을때 메모이제이션을 적용하지 않는다면 시간 초과가 발생하게 된다. 메모이제이션은 이 문제에서 원하는 DP[N] = N으로 만들수 있는 최소 사면체 수로 적용하면 된다.

PS 처음에는 Top-down으로 풀려고 했는데 어쩌다보니 Bottom-up 풀이가 되어버렸다. 나중에 Top-down으로도 다시 짜봐야겠다.

//mincost[n] = n으로 만들수 있는 최소 사면체 수
//sum[n] = n 사이즈 사면체를 만드는데 필요한 대포알의 수

#include <stdio.h>
#define INT_MAX 98765431
int sum[130]={0},mincost[300001]={0};
int min(int a, int b){
	return a<b?a:b;
}
int solve(int ball, int pos,int count){
	if(ball<0) return INT_MAX;
	if(mincost[ball]) return mincost[ball];
	if(pos<1) return INT_MAX;
	if(ball == 0) return count;
	mincost[ball] = min(solve(ball-sum[pos],pos,count)+1, solve(ball,pos-1,count));
	return mincost[ball];
}
int main(){
	int i=0,n,maxp;
	scanf("%d",&n);
	while(++i){
		sum[i] = i*(i+1)*(i+2)/6;
		if(sum[i] >= 300000) break;
	}
	maxp=i-1;
	for(i=1;i<=n;i++){
		solve(i,maxp,0);
	}
	printf("%d",mincost[n]);
}