1463 1로 만들기

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

1로 만드는 최소 연산 횟수는 1에서 N까지 만드는 최소 연산 횟수와 같다. 이를 d[i]이라 하면 이전에 올 수 있는 연산들 중 최소에 1을 더하면 된다. d[i]=min(d(i-1],d[i/3],d[i/2])+1

Top-Down 구현

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,d[1000001];
 
int go(int n)
{
    if(n==1 || d[n]) return d[n];
    d[n]=go(n-1)+1;
    if(n%3==0) d[n]=min(d[n],go(n/3)+1);
    if(n%2==0) d[n]=min(d[n],go(n/2)+1);
    return d[n];
}
 
int main()
{
    scanf("%d",&n);
    printf("%d",go(n));
    return 0;
}

Bottom-Up 구현

#include <cstdio>
 
int n,d[1000001];
 
int main()
{
    for(int i=2;i<1000001;i++)
    {
        d[i]=d[i-1]+1;
        if(i%3==0 && d[i/3]+1<d[i])
            d[i]=d[i/3]+1;
        if(i%2==0 && d[i/2]+1<d[i])
            d[i]=d[i/2]+1;
    }
    scanf("%d",&n);
    printf("%d",d[n]);
    return 0;
}