[백준][12852] 1로 만들기 2

문제

제약 확인

시간 제한이 0.5초 이므로 50’000’000 번 이내 연산으로 결과를 출력해야 합니다.
입력 크기가 \(10^6\) 이므로 만약 \(O(N^2)\) 인 경우 100’000’000’000 가 되므로
시간 복잡도가 \(O(N)\) 가 보장되는 알고리즘이 필요합니다.

알고리즘 선택하기

최소 횟수 라는 키워드로 최단 경로 알고리즘 혹은 다이나믹 프로그래밍을 고려할 수 있지만
다이나믹 프로그래밍의 핵심 개념인 Top-down, Bottom-up 에 문제가 적합하기 때문에
다이나믹 프로그래밍으로 풀어보겠습니다.

문제 해결하기

다이나믹 프로그래밍을 풀기 위해서는 작은 문제와 큰 문제 사이 점화식 을 구해야 합니다.
먼저, 10부터 2까지 차례대로 최소 횟수를 모두 직접 구해보겠습니다.

규칙을 찾아보면 N 에서 최소 횟수는 (직전 최소 연산 횟수) + 1 이라는 것을 확인할 수 있습니다.
따라서 다이나믹 프로그래밍 기법 중 Bottom-up 방식이 적합합니다.

N 번째 최소 연산 횟수는 3가지 연산 방법 중 가장 작은 값에 1을 더한 값이므로 점화식은 다음과 같습니다.

\(DP[N] = 1 + min(DP[N / 3], DP[N / 2], DP[N - 1])\)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cout.tie(0)->sync_with_stdio(false);
    cin >> N;

    vector<vector<int>> result(N + 1, vector<int>());
    result[1].emplace_back(1);

    for(int curr = 2; curr <= N; ++curr) {
        int MIN = result[curr - 1].size();

        result[curr] = result[curr - 1];

        if((curr % 3 == 0) && (result[curr / 3].size() < MIN)) {
            MIN = result[curr / 3].size();
            result[curr] = result[curr / 3];
        }
        if((curr % 2 == 0) && (result[curr / 2].size() < MIN)) {
            MIN = result[curr / 2].size();
            result[curr] = result[curr / 2];
        }

        result[curr].emplace_back(curr);
    }

    cout << result[N].size() - 1 << "\n";
    for(int i = result[N].size() - 1; i >= 0; --i) {
        cout << result[N][i] << " ";
    }

    return 0;
}

반복문 안에서 작은 문제를 큰 문제로 합치는 방법은
먼저, 직전 최소 횟수(result[curr - 1].size()) 를 현재 최솟값(MIN)으로 저장합니다.
현재 N 값(curr)까지의 최소 횟수 값을 curr - 1 위치의 최솟값으로 저장합니다.
그리고 2, 3으로 나누어 떨어지면서 MIN 보다 작은 값이 존재할 때,
현재 값(result[curr])을 갱신합니다.
마지막으로 현재 값을 만들기 위한 숫자들을 배열에 넣으면 정답을 구할 수 있습니다.

참고

[BOJ_12852] 1로 만들기 2
D.JOUNG 님 블로그