난이도 : 실버 1
유형 : DP, 역추적
https://www.acmicpc.net/problem/12852

문제 접근

1. X가 3으로 나누어 떨어지면, 3으로 나누다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이 세가지 방법을 이용하여 가장 효율적으로 1을 만드는 문제이다.

이전에 이 문제를 푼적이 있는데 1로 만들기2 이 문제는 어떻게 1이 나오게 되었는지까지 '역추적'하여 출력하는 문제이다.

dp를 이용하여 dp[n]일 경우 n이 1로 만들어지는 최소 횟수를 저장하고
prev 배열을 만들어서 prev[i]라면 i로 가기 바로 전 숫자를 저장하여 역추적할 때 쓰는 방식으로 코드를 구현했다.

코드 및 풀이

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n + 1) # 최소 연산 횟수
prev = [0] * (n + 1) # 어디서 왔는 지 기록

for i in range(2, n+1):
    # 1을 뺀 경우로 초기화
    dp[i] = dp[i-1] + 1
    prev[i] = i - 1

    # 2로 나룰 수 있는 경우
    if i % 2 == 0 and dp[i] > dp[i//2] + 1:
        dp[i] = dp[i//2] + 1
        prev[i] = i//2

    
    # 3으로 나눌 수 있는 경우
    if i % 3 == 0 and dp[i] > dp[i//3] + 1:
        dp[i] = dp[i//3] + 1
        prev[i] = i//3

# 출력
print(dp[n])

# 경로 복원
path = []
cur = n
while cur != 0:
    path.append(cur)

    if cur == 1:
        break
    cur = prev[cur]

print(*path)

bottom-up 방식으로 dp를 구현하였고, prev 배열을 통해 그 전 숫자를 저장하여 숫자들의 경로를 표현할 수 있었다.