201030 1로 만들기 1463번(C++) --잘 모르겠습니다

www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제:

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이 3가지 연산을 이용해서 입력 값을 1로 만들고, 연산을 사용하는 횟수의 최소 값을 출력합니다.

최소 값은 모르겠고, 그냥 if로 분기해서 풀면 될 것 같다는 생각이 들었습니다.

 

이렇게 코드를 작성하니 답이 안 나왔습니다. 그래서 찾아보니 다른 분들은 동적 프로그래밍 방법을 사용하고 배열을 이용해 값을 기록 해나갔습니다.

정말 어이가 없었죠 왜 동적 프로그래밍을 사용하는지도 모르겠고, 입력 값이 1개인데 배열을 왜 쓰는지를 모르겠습니다. 

 

코드:

#include <iostream>
using namespace std;

int main(){
    int x;
    cin >> x;
    
    int count = 0;
    while(x!=1){
        if(x % 2 ==0){
            x /= 2;
            ++count;
        }
        if(x % 3 == 0){
            x /= 3;
            ++count;
        }
        else if(x % 2 != 0 && x % 3 != 0){
            --x;
            ++count;
        }
    }
    cout << count;
    return 0;
}