문제

코드

#include <iostream>
using namespace std;
int d[10000000];
int main()
{   
    int n;
    cin>>n;
    d[1]=0;
    for(int i=2;i<=n;i++)
    {	d[i]=d[i-1]+1;
        if(i%2==0 && d[i]>d[i/2]+1)
        {
            d[i]=d[i/2]+1;
        }
          if(i%3==0 && d[i]>d[i/3]+1)
        {
            d[i]=d[i/3]+1;
        }
    }
    cout<<d[n];
    return 0;
}

풀이

숫자 n을 1로 만드는 방법은 n-1 + 1 or n/2 + 1 or n/3 + 1 을 1로 만드는 것과 동일한것을 이용해줌, 다이나믹프로그래밍을 이용해 d[i]에 값을 저장하여 풀어주었다