[백준] 12852번-(Python 파이썬) - DP

문제링크 : https://www.acmicpc.net/problem/12852

이번 문제는 dp알고리즘을 이용해 간단하게 풀 수 있었다.

먼저 저장하고 혹시 값이 더 크다면 작은 값으로 바꿔주면 되는 문제이다.
조금 애를 먹었던게 순서도 같이 출력해야한다는 부분이었는데 그 부분은 순서를 담을 배열을 추가하여 구현하였다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0, []] for _ in range(n + 1)]
dp[1][0] = 0
dp[1][1] = [1]

for i in range(2, n + 1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 3][0] + 1
        dp[i][1] = dp[i // 3][1] + [i]
    if i % 2 == 0 and dp[i // 2][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 2][0] + 1
        dp[i][1] = dp[i // 2][1] + [i]

print(dp[n][0])
print(*reversed(dp[n][1]))

문제를 풀고 다른 분들의 코드를 보며 공부를 하다 알게 된 코드인데
속도는 dp에 비해 살짝 느리지만 deque를 이용하여 간단하게 풀어낸 코드에 인상이 깊어 다시 한번 제출을 하게 만든 코드이다.

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
q = deque()
q.append([n])
ans = []

while q:
    a = q.popleft()
    x = a[0]
    if x == 1:
        ans = a
        break

    if x % 3 == 0:
        q.append([x // 3] + a)

    if x % 2 == 0:
        q.append([x // 2] + a)
    
    q.append([x - 1] + a)

print(len(ans) - 1)
print(*ans[::-1])