백준_1463 : 1로 만들기 - C++

문제

---

문제 해석

- 정수 X 가 주어 질 때 아래 연산들을 사용 하여 가장 적은 연산으로 1을 만들면 되는 문제이다.

---

알고리즘

- DP 문제이기 때문에 규칙성만 찾게 되면 쉽게 풀 수 있는 문제이다.

- 이 문제에서 연산은 "/3", "/2", "-1" 세 종류가 있다.

- 세가지 연산을 모두 할 수 있는 6을 예시로 설명을 이어가 보도록 하겠다.

  - 6은 "-1" 연산을 통해 5를 만들 수 있기 때문에 DP[6] == DP[5] + 1 (5가 1이 되기까지 연산 횟수 + 1)이라고 볼 수 있다.

  - 또 6은 "/2" 연산을 통해 3을 만들 수 있기 때문에 DP[6] == DP[3] + 1도 될 수 있다.

  - 마찬가지로 6은 "/3" 연산을 통해 2를 만들 수 있기 때문에 DP[6] == DP[2] + 1도 될 수 있다.

- 즉 위 상황에서는 DP[6]은 DP[5]+1, DP[3]+1, DP[3]+1중 최소 값이라고도 볼 수 있다.

- 만약 10 처럼 연산중 일부가 불가능한 수는 해당 경우의 수를 제외 하고 최소 값을 찾아 주면 된다.

---

코드

#include <iostream>
#include <cmath>
using namespace std;

int DP[1000001];

int main(){
    DP[1] = 0;
    DP[2] = 1;
    DP[3] = 1;

    int tmp;
    cin >> tmp;

    for(int i = 1; i <= tmp; i++){
        if(i > 3){
            DP[i] = DP[i-1] + 1;
            if(i % 2 == 0) DP[i] = min(DP[i/2] + 1, DP[i]);
            if(i % 3 == 0) DP[i] = min(DP[i/3] + 1, DP[i]);
        }
    }
    cout << DP[tmp];
}