🟩 [백준] [Python] [Class4] 12852번_1로 만들기 2

문제

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

12852번: 1로 만들기 2

풀이

BFS를 이용한 풀이

# 백준 12852번 문제 - 1로 만들기 2
from collections import deque

n = int(input())
q = deque()
q.append((n,[n]))
visited = [0]*(n+1)

while q:
    num,ans = q.popleft()
    if num == 1:
        print(len(ans)-1)
        print(*ans)
        break
    if not visited[num]:
        visited[num]=1
        if num%3==0:
            q.append((num//3,ans+[num//3]))
        if num%2==0:
            q.append((num//2,ans+[num//2]))
        q.append((num-1,ans+[num-1]))

 

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]))