[백준] 12852번 : 1로 만들기 2 - C++

백준 12852번 : 1로 만들기 2

등급 : Silver I

12852번: 1로 만들기 2 (acmicpc.net)

12852번: 1로 만들기 2

사용 알고리즘 : Dynamic Programming

사용 자료구조 : -

 

처음엔 BFS 문제인 줄 알았으나, 경로 저장에 적합하지 않고 시간 초과 발생.

각 정점에 대한 최소 횟수가 정해져 있으므로, 최단 거리 값을 구해 저장하는 다이나믹 프로그래밍 기법 이용.

---

  1. 크기가 1000000인 DP 배열과 각 정점의 직전 점을 저장할 Before 배열 생성.

  2. 1일 때 까지의 경로를 구하는 것이므로, N=1인 경우에는 방법이 0개. → DP[1] = 0을 저장

  3. 2부터 N까지의 DP를 Bottom-Up 방식으로 구현.

       1) 1씩 증가되는 경우가 가장 큰 값을 지니게 되면서 항상 적용 가능하므로 1씩 증가되는 경우를 먼저 저장.

           - DP[i] = DP[i - 1] + 1 // 이전보다 경로의 갯수가 1개 늘어나므로, 이전 정점의 값보다 1을 늘려줌.

           - 이전 좌표가 하나 전 위치가 되므로, Before[i] = i - 1

       2) 3으로 나눌 수 있고, 그 값이 현재 DP값보다 작은 경우 DP값을 갱신해준다.

           - DP[i] = DP[i / 3] + 1

           - 예시. DP[9] = 3 (1 → 3 → 9), DP[3] = 2 (1 → 3)이므로, DP[9] = DP[3] + 1

           - 이전 좌표가 3으로 나눈 위치가 되므로 Before[i] = i / 3

       3) 2로 나눌 수 있고, 그 값이 현재 DP값보다 작은 경우 DP값을 갱신해준다.

           - DP[i] = DP[i / 3] + 1

           - 이전 좌표가 2로 나눈 위치가 되므로 Before[i] = i / 2

  4. DP[N]의 값을 출력하고, Before[N]을 따라 경로를 출력.

---

#include <iostream>

using namespace std;
int dp[1000000];
int before[1000000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    dp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + 1;
        before[i] = i - 1;

        if (i % 3 == 0 && dp[i] > dp[i / 3] + 1)
        {
            dp[i] = dp[i / 3] + 1;
            before[i] = i / 3;
        }
        if (i % 2 == 0 && dp[i] > dp[i / 2] + 1)
        {
            dp[i] = dp[i / 2] + 1;
            before[i] = i / 2;
        }
    }
    cout << dp[n] << "\n";
    while (n != 0)
    {
        cout << n << " ";
        n = before[n];
    }
}