백준 문제 풀이 - 1로 만들기 1463번

📜 문제 이해하기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

💡 문제 재정의

숫자를 1로 만들기위해 위해서 위 메소드를 수행할 때 가장 적은 연산 수를 출력하자.

✏️ 계획 수립

다이나믹 프로그래밍으로 문제를 해결할 수 있다.
dp에서 홀수에서 -1을 하면 짝수이기 때문에 1을 빼는건 한번 밖에 없다. 따라서 dp에서 홀수라면 -1를 적용한 값에 1을 더한 값을 기본 값으로 둔다.
그 후 3으로 나눠진다면 dp[i%3] + 1, 2로 나눠지면 dp[i%2] + 1를 더해주면 된다.

💻 계획 수행

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<int> dp;
    int X;
    // 초기화
    dp.push_back(0);
    dp.push_back(0);

    cin >> X;
    for (int i = 2; i <= X; i++) {
        dp.push_back(dp[i - 1] + 1);
        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1);
        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1);
    }

    cout << dp[X];
}

🤔 회고

시간 복잡도때문에 다이나믹 프로그래밍을 사용하지 않는다면 풀 수 없는 문제였다.