백준 : 1로 만들기 1463번

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

1463번: 1로 만들기

 

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long int n,a[1000001]={0,},i;
    scanf("%lld",&n);

    for(i=2;i<=n;i++)
    {
        a[i]=a[i-1]+1;
        if(i%2==0 && a[i] > a[i/2] + 1)
            a[i] = a[i/2] + 1;
        if(i%3==0 && a[i] > a[i/3] + 1)
            a[i] = a[i/3] + 1;
    }

    /*
    for(i=1; i<=n; i++)
        printf("%lld : %lld  \n",i, a[i]);
        */
    printf("%d", a[n]);
    return 0;
}