백준 1463 c++ 풀이

알고리즘 분류: 다이나믹 프로그래밍

코드:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main(){
	int a;
	cin>>a;
	
	vector<int> v(1000001);
	for(int  i= 2; i<=a; i++){
		v.at(i) = v.at(i-1) + 1;
		if(i%2==0) v.at(i) = min(v.at(i), v.at(i/2) + 1);
		if(i%3 == 0) v.at(i) = min(v.at(i), v.at(i/3) + 1);
	}
	cout<<v.at(a)<<endl;

}