BOJ 1463 [1로 만들기]

BOJ 1로 만들기 : https://www.acmicpc.net/problem/1463

안녕하세요. 이번 문제는 백준 온라인 저지의 "1로 만들기" 입니다.

우선, 정수 1에서 1로 가기위해 사용되는 연산 수는 0입니다. (arr[1] = 0)

그 다음, 2, 3에서 1로 가기위해 사용되는 연산 수는 1입니다. (2 / 2 or 2 - 1 = 1,   3 / 3 = 1  -> arr[2], arr[3] = 1)

4부턴 1로 가는 방법이 여러가지입니다. (4 / 2 = 2 / 2 = 1, 4 - 1 = 3 / 3 = 1 -> arr[4] = 2)

이제부터 N에 대해 보겠습니다. 총 세 가지 값을 비교하면 됩니다.

만약 N을 3으로 나눌 수 있으면, arr[N] = arr[N / 3] + 1이 됩니다.

또, 2로 나눌 수 있으면 arr[N / 2] + 1이 됩니다.

마지막으로 arr[N - 1] + 1이 있습니다.

이 세 값을 비교해, 가장 작은 값이 arr[N]이 됩니다.

#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;
    int* arr= new int[N+1];
    arr[1] = 0;
    if(N == 2) {
        arr[2] = 1;
    }
    else if(N > 2){
        arr[2] = 1;
        arr[3] = 1;
    }
    for(int i=4; i<=N; i++) {
        int temp = 999999;
        if(i % 3 == 0) {
            if(temp > arr[i/3] + 1)
                temp = arr[i/3] + 1;
        }
        if(i % 2 == 0) {
            if(temp > arr[i/2] + 1)
                temp = arr[i/2] + 1;
        }
        if(temp > arr[i-1] + 1)
            temp = arr[i-1]+1;
        arr[i] = temp;
    }
    cout << arr[N];
    return 0;
}