[백준] 1463 1로 만들기

맨 처음에는 0.1초가 나오도록 값을 입력받으면 바로 해결하는 프로그램을 짜려고 했는데, 이것은 조금 힘들 거 같아서 dp로 생각을 돌렸다. 

 

맨 처음에는 1을 뺀 배열의 값을 참조해서 1을 더해주고

두번짼는 2로 나눠지면 2로 나눠진 배열에 1을 더해주고

마지막에는 3으로 나눠지면 3으로 나눠진 배열에 1을 더해준다. 

 

고려하는 순서가 

-1 , /2, /3인 이유는 큰 수를 나눌수록 가장 작은 횟수를 찾을 수 있기 때문이다. 

#include <iostream>
using namespace std;
int arr[1000001];
int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        arr[i] = arr[i - 1] + 1;

        if (i % 2 == 0) {
            if (arr[i] >= arr[i / 2] + 1) {
                arr[i] = arr[i / 2] + 1;
            }
            
        }
        if (i % 3 == 0) {
            if (arr[i] >= arr[i / 3] + 1) {
                arr[i] = arr[i / 3] + 1;
            }

        }
    }
    cout << arr[n];


    return 0;
}