[백준 1463] 1로 만들기

https://www.acmicpc.net/problem/1463

n번째 숫자의 값 은 n-1번째, n/2번재, n/3번째 숫자에서 연산을 한 번 추가하여 구할 수 있다. 세 연산 중 가장 작은 값을 선택.

n번째 숫자의 값 <- min( n-1번째 숫자의 값 +1, n/2번째 숫자의 값 +1, n/3번째 숫자의 값+1)

(단 n/2, n/3이 존재하지 않는 경우 infinite)

Pseudo code

arr[1,000,001]
arr[1] <- 0
arr[2] <- 1
arr[3] <- 1
for i <- 4 ... 10^6 do
    if i % 2 == 0 then
        temp1 <- arr[i/2] +1
    else
        temp1 <- inf
    if i % 3 == 0 then
        temp2 <- arr[i/3] +1
    else
        temp2 <- inf
    min(temp1, temp2, arr[i-1]+1)
print arr[n]

C++ code

#include <iostream>
using namespace std;
int my_min(int n1, int n2, int n3){
    int min1;
    if(n1 > n2)
        min1 = n2;
    else
        min1 = n1;
    if(min1 > n3)
        min1 = n3;
    return min1;
}
int main(){
    int n;
    cin >> n;
    int *arr = new int[n+1];
    arr[1] = 0;
    arr[2] = 1;
    arr[3] = 1;
    int temp1, temp2;
    for(int i = 4; i <= n ; i++){
        if(i % 2 == 0)
            temp1 = arr[i/2]+1;
        else
            temp1 = 987654321;
        if(i % 3 == 0)
            temp2 = arr[i/3]+1;
        else
            temp2 = 987654321;
        arr[i] = my_min(temp1, temp2, arr[i-1]+1);
    }
    cout << arr[n];
    return 0;
}