[백준/BOJ] 백준 코딩 알고리즘 1463번/C++

백준 코딩 알고리즘 문제 1463번

 

백준 코딩 알고리즘 문제 1463번 풀이 - 사용 언어: C++

#include <iostream>
#include <algorithm>
#define MAX 1000000
 
using namespace std;
 
int operNum[MAX + 1];
 
int main() {
 
    int X;
    cin >> X;
 
    operNum[0] = 0;
    operNum[1] = 0;
    operNum[2] = 1;
    operNum[3] = 1;
 
 
    //연산 횟수를 저장하는 배열을 최대 크기까지 채운다
    for (int i = 4; i <= MAX; i++) {
        //각 수가 조건에 맞는 가능한 연산에 따라서 배열의 값(연산의 횟수)를 채운다
        if (i % 2 == 0 && i % 3 == 0) {
            operNum[i] = min(1 + operNum[i - 1], min(1 + operNum[i / 2], 1 + operNum[i / 3]));
        }
        else if (i % 2 == 0) {
            operNum[i] = min(1 + operNum[i / 2], 1 + operNum[i - 1]);
        }
        else if (i % 3 == 0) {
            operNum[i] = min(1 + operNum[i / 3], 1 + operNum[i - 1]);
        }
        else {
            operNum[i] = 1 + operNum[i - 1];
        }
    }
 
    cout << operNum[X] << endl;
 
    return 0;
 
}