[Python] 백준 12852 - 1로 만들기 2

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

12852번: 1로 만들기 2

사용하는 횟수의 최솟값은 "1로 만들기"에서 이미 다뤘던 시리즈 문제다.

이번 문제는 연산이 진행되면서 방법에 포함된 수도 출력해야하는 문제다. 어려웠다면 아마 여기서 어려웠을 것 같다.

 

 

문제를 보자마자 DP 문제구나 싶었지만 BFS로도 풀 수 있을 것 같아서 BFS로 먼저 풀어봤다.

Python으로 제출했더니 TLE가 나왔고 Pypy로 제출하니 통과된 코드다.

from collections import deque

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


def bfs():
    while q:
        arr = q.popleft()

        x = arr[0]
        if x == 1:
            return arr

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

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

        q.append([x-1]+arr)

res = bfs()
print(len(res)-1)
print(*res[::-1])

 

다음으로 DP로도 풀었는데 확실히 DP가 빠르다.

n = int(input())

dp = [0]*1000001

for i in range(2,n+1):
    
    # 1을 뺀 경우
    dp[i] = dp[i-1] + 1
    
    # 2로 나누어 떨어지면
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[n])

res = [n]
now = n
temp = dp[n] - 1

# n부터 하나씩 줄여나가면서 순서 찾기
for i in range(n, 0, -1):
    if dp[i] == temp and (i+1 == now or i*2 == now or i*3 == now):
        now = i
        res.append(i)
        temp -= 1

print(*res)

 

DP 잘하고 싶다...