#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]에 값을 저장하여 풀어주었다