1463: 1로 만들기

#include "bits/stdc++.h"

using namespace std;

int jumper[10000001];

int main() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
    	if (i * 3 < 10000001 && !jumper[i * 3])
    		jumper[i * 3] = jumper[i] + 1;
    	else
    		jumper[i * 3] = min(jumper[i * 3], jumper[i] + 1);

    	if (i * 2 < 10000001 && !jumper[i * 2])
    		jumper[i * 2] = jumper[i] + 1;
    	else
    		jumper[i * 2] = min(jumper[i * 2], jumper[i] + 1);

    	if (i + 1 < 10000001 && !jumper[i + 1])
    		jumper[i + 1] = jumper[i] + 1;
    	else
    		jumper[i + 1] = min(jumper[i + 1], jumper[i] + 1);
    }

    cout << jumper[n];

}

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

int arr[1000001];

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

    int i, n;
    cin >> n;

    arr[2] = 1;
    arr[3] = 1;

    for (int i = 4; i <= n; i++){
    	arr[i] = arr[i - 1] + 1;
    	if (i % 2 == 0)
    		arr[i] = min(arr[i / 2] + 1, arr[i]);
    	if (i % 3 == 0)
    		arr[i] = min(arr[i / 3] + 1, arr[i]);
    }

    cout << arr[n];

}