[C++] BOJ 백준 1463 1로 만들기

문제링크 : https://boj.kr/1463

DP를 사용하면 이전 단계의 계산 결과를 그대로 활용할 수 있는 문제이다.

문제에서 힌트로 주어진 10을 연산하는 방법을 생각해보면

10 -> 5 -> 4 -> 2 -> 1

10 -> 9 -> 3 -> 1

이런 방법이 나올 수 있을 것이다.

10이라는 숫자는 바로 2로 나눌 수 있는 숫자이지만 -1을 한 후에 연산하면 횟수가 더 적은 것을 확인할 수 있다.

따라서, 어떤 숫자가 2나 3으로 나눌 수 있을 지라도 -1을 했을 때와 비교한 후 최소 횟수가 어느쪽인지를 취하면 문제를 풀 수 있게 된다.

1을 뺀 후에 연산하는 방법이 어떤 경우에도 허용이 되기 때문에 먼저 1을 빼서 연산한 횟수를 계산한다.

현재 숫자에서 1을 뺀 연산은 이전 단계에서 이미 연산이 되었기 때문에 dp[i-1]에다가 연산 횟수 1회만 추가하면 된다.

그리고 3으로 나누어지거나 2로 나누어지거나 어떤 연산을 우선적으로 해도 상관은 없다.

그 값은 이미 구해져있기 때문이다.

이 역시 dp[i/3]이나 dp[i/2]에다가 연산 횟수 1회만 추가하면 된다.

// BOJ 1463 1로 만들기
#include <bits/stdc++.h>
 
using namespace std;
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
    vector<int> dp(num + 1);
 
    // 초기 기저 값
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    for (int i = 4; i <= num; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1);
        else if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1);
    }
    cout << dp[num];
 
    return 0;
}