백준 1463(동적 계획법)

#include 
#include 

int main(void)
{
	int n;
	int * a =NULL;
	int i;
	scanf("%d",&n);
	a=calloc(n+1,sizeof(int));
	for(i=1;i<=n;i++){
		a[i]=10000000;
	}
	
	i=n;
	a[i]=0;
	for(i;i>=1;i--)
	{
		if(a[i]!=10000000)
		{
			if(i/3 >=1 && i%3==0){
				if(a[i/3] > a[i]+1){
					a[i/3]=a[i]+1;
				}
			}
			if(i/2 >=1 && i%2==0){
				if(a[i/2] > a[i]+1){
					a[i/2]=a[i]+1;
				}
			}
			if(i-1 >=1 ){
				if(a[i-1] > a[i]+1){
					a[i-1]=a[i]+1;
				}
			}
			
			
		}
	}
	printf("%d",a[1]);
	
	return 0;	
}

n 번째 값을 입력받으면 n을 0으로 만든다. 그리고 n을 3으로 나눠지면 그 값을 a[n]의 값 +1 을 해준다.. 마찬가지로 2도 -1도 ... 자세한 설명은 생략한다.