[12852번] 1로 만들기 2

문제 출처 :

https://www.acmicpc.net/problem/12852

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

이 문제를 풀기 전 

[1463번] 1로 만들기 :: http://www.crocus.co.kr/443 문제를 먼저 풀 것을 추천한다.

위의 문제는 x값에서 1로 갈때 최단 거리를 묻고 있지만, 이번 문제는 최단 거리의 경로를 표현해달라 요구하고 있다.

결국 trace배열을 이용하여 어느 값이 갱신되었는지 확인하고, 그 갱신된 값의 경로를 trace[현재] = 추적경로로 지정해주면 된다.

나머지 설명은 위의 링크에 포함되어있으니 확인하면 될 것 같다.

소스 코드 : 

#include <stdio.h>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int arr[1000002];
int DP[1000002] = { 0,0,1,1 };
int trace[1000002] = { 0, 0, 1, 1 };
 
int main()
{
    int n;
    int a, b, c, d, e, f;
    int empty = 100;
    scanf("%d", &n);
 
 
    for (int i = 4; i <= n; i++)
    {
        a = empty; b = empty; c = empty; d = empty; e = empty;
 
        if ((i - 1) % 3 == 0)
            a = DP[(i - 1) / 3] + 2;
 
        if (i % 6 == 0)
            b = DP[i / 3] + 1;
 
        if (i % 2 == 0)
            c = DP[i / 2] + 1;
 
        if (i % 3 == 0)
            d = DP[i / 3] + 1;
 
        e = min({DP[i - 1] + 1, DP[i - 2] + 2, DP[(i - 1) / 2] + 2, empty, empty});
 
        DP[i] = min({a, b, c, d, e});
 
        if (DP[i] == a)
        {
            trace[i] = (i - 1);
            trace[i - 1] = (i - 1) / 3;
        }
        else if (DP[i] == b)
            trace[i] = i / 3;
        else if (DP[i] == c)
            trace[i] = i / 2;
        else if (DP[i] == d)
            trace[i] = i / 3;
        else if (DP[i] == e)
        {
            if (e == DP[i - 1] + 1)
                trace[i] = i - 1;
            else if (e == DP[i - 2] + 2)
            {
                trace[i] = i - 1;
                trace[i - 1] = i - 2;
            }
            else
            {
                trace[i] = (i - 1);
                trace[i - 1] = (i - 1) / 2;
            }
        }
    }
    printf("%d\n", DP[n]);
 
    while (n != 1)
    {
        printf("%d ",n);
        n = trace[n];
    }
    printf("1");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>