[BOJ_C++] 12852번 : 1로 만들기 2

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int dp[1000001];
int visited[1000001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(dp, 0, sizeof(dp));
    memset(visited, 0, sizeof(visited));

    int n; cin >> n;
    
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        visited[i] = i - 1;

        if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
            dp[i] = dp[i / 2] + 1;
            visited[i] = i / 2;
        }

        if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
            dp[i] = dp[i / 3] + 1;
            visited[i] = i / 3;
        }
    }

    printf("%d\n", dp[n]);
    while (n > 0) {
        printf("%d ", n);
        n = visited[n];
    }

    return 0;
}

• 백준 1463번 : 1로 만들기에서 방문한 곳을 출력하는 내용이 추가된 문제이다. 따라서 1463번과 최소 횟수를 구하는 것은 동일하다.
• 방문한 곳을 저장하기 위해 visited 배열을 만들어 주었다.
• 현재 있는 곳이 i일 때 방문한 곳과 동일하게 i - 1 | i / 2 | i / 3 값 중 해당하는 값을 저장해두면 된다.
• 출력할 땐 거꾸로 n을 출력하고 n을 인덱스에 들어있는 값으로 바꾸어 전 위치로 이동해준다.

결과