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

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

12852번: 1로 만들기 2

 

import sys
input = sys.stdin.readline


def setDp(start):
    todo = [start]
    dp[start] = (0, 0)

    while todo:
        cur = todo.pop(0)

        if cur == 1:
            break

        if cur % 3 == 0 and dp[cur//3][0] > dp[cur][0] + 1:
            dp[cur//3] = (dp[cur][0] + 1, cur)
            todo.append(cur//3)

        if cur % 2 == 0 and dp[cur//2][0] > dp[cur][0] + 1:
            dp[cur//2] = (dp[cur][0] + 1, cur)
            todo.append(cur//2)

        if dp[cur-1][0] > dp[cur][0] + 1:
            dp[cur-1] = (dp[cur][0] + 1, cur)
            todo.append(cur-1)


def printPath():
    path = []
    cur = 1

    while cur != 0:
        path.append(cur)
        cur = dp[cur][1]

    print(*reversed(path))


if __name__ == '__main__':
    N = int(input())
    dp = [(float('inf'), 0)]*(N+1)

    setDp(N)

    print(dp[1][0])
    printPath()

 

N부터 시작하는 BFS를 사용하였다. 가령 현재 노드가 12이면, next는 4, 6, 11이다. 그리고, dp에 특정 지점에서의 (비용, 이전 노드)를 저장한다.

BFS를 진행하면서, 현재 노드가 1이면 탐색을 끝낸다. 그리고 각 3개의 케이스에 대해서, 3, 2로 나누어지는지, 그리고 DP의 비용이 최소인지를 검사하여 DP를 갱신하고 큐에 원소를 추가한다.

 

이렇게 탐색을 하면 DP에 기록이 남으므로, 이를 통해 탐색하여 path를 출력해준다.