BOJ-12852 - Python

정수 n을 입력받은 후 해당 정수가 3으로 나누어 떨어지면 3으로 나누며, 2로 나누어 떨어지면 2로 나누기, 1을 빼기 3개의 연산이 가능할 때 이를 적절히 사용해 1로 만들 때 연산을 사용하는 횟수의 최솟값과 방법에 포함되어 있는 수를 출력하는 문제. 기본 1로 만들기에서 방법에 포함되어 있는 수를 추가한 문제. 첫 번째 풀이는 힙을 이용하여 그래프 탐색과 같은 방법으로 연산하며 1일 때 필요한 값을 반환하도록 풀었으나 시간초과 결과를 받게 되었다. 두 번째 풀이는 i가 1로 만들어질 때 필요한 값을 저장하는 배열을 이용하여 다이내믹 프로그래밍 방법을 이용하여 풀었다. 값이 갱신될 때 방법에 포함되어 있는 수를 저장하는 2차원 배열에 값을 추가하도록 풀었다.

# import heapq
# import sys
# INF = sys.maxsize
#
# def solve():
#     q = []
#     # cnt, visit, now
#     heapq.heappush(q, [0, [n], n])
#     visit = [INF for _ in range(n+1)]
#
#     while q:
#         cnt, route, now = heapq.heappop(q)
#         if now == 1:
#             return cnt, route
#
#         visit[now] = cnt
#
#         heapq.heappush(q, [cnt+1, route+[now-1], now-1])
#
#         div3 = now // 3
#         if now % 3 == 0:
#             heapq.heappush(q, [cnt+1, route+[div3], div3])
#
#         div2 = now // 2
#
#         if now % 2 == 0:
#             heapq.heappush(q, [cnt+1, route+[div2], div2])
#
#
# n = int(input())
# cnt, route = solve()
# print(cnt)
# print(*route)



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

dp[1] = 0
paths[1] = [1]

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1
    paths[i] = paths[i-1] + [i]

    div3 = i // 3
    if i % 3 == 0 and dp[i] > dp[div3] + 1:
        dp[i] = dp[div3] + 1
        paths[i] = paths[div3] + [i]

    div2 = i // 2
    if i % 2 == 0 and dp[i] > dp[div2] + 1:
        dp[i] = dp[div2] + 1
        paths[i] = paths[div2] + [i]

print(dp[n])
print(*reversed(paths[n]))

Written by@hyesungoh
Learning every moment

InstagramGitHubLinkedIn