[C++][백준 1463][DP] 1로 만들기 - 컴도리돌이

문제

---

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

코드

---

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

using namespace std;


int n;

int main(void)
{
    cin >> n;
    vector<long long> v(n+1,0);
    for(long long i=2; i<= n ; i++)
    {
        v[i] = v[i-1] + 1;
        if(i % 2 == 0) v[i] = min(v[i],v[i/2] + 1);
        if(i % 3 == 0) v[i] = min(v[i],v[i/3] + 1);
    }

    cout << v[n];
}