54 lines
1.2 KiB
Python
54 lines
1.2 KiB
Python
# 1로 만들기 2
|
|
|
|
import sys
|
|
|
|
input = sys.stdin.readline
|
|
|
|
def solution():
|
|
n = int(input().rstrip())
|
|
|
|
dp = [float('inf')]*(n+1)
|
|
dp[n] = (0, n)
|
|
|
|
ways = [3, 2]
|
|
|
|
for i in range(n-1, 0, -1):
|
|
min_count = float('inf')
|
|
min_from = -1
|
|
for way in ways:
|
|
before = i * way
|
|
if before > n:
|
|
continue
|
|
if min_count > dp[before][0]:
|
|
min_count = dp[before][0]
|
|
min_from = before
|
|
before = i + 1
|
|
if before > n:
|
|
continue
|
|
if min_count > dp[before][0]:
|
|
min_count = dp[before][0]
|
|
min_from = before
|
|
|
|
dp[i] = (min_count+1, min_from)
|
|
|
|
result = [1]
|
|
idx = 1
|
|
while idx < n:
|
|
idx = dp[idx][1]
|
|
result.append(idx)
|
|
|
|
print(dp[1][0])
|
|
print(*result[::-1])
|
|
|
|
return
|
|
|
|
|
|
solution()
|
|
|
|
"""
|
|
걸린 시간: 25분
|
|
|
|
시간 복잡도: dp 테이블 채우고 역추적까지 O(n)이다.
|
|
|
|
해설: 1463(1로 만들기 문제)번에서 과정을 출력하는 과정이 추가되었다. 이는 dp 테이블을 채울 때, 어디서 왔는지만 기록해주면 마지막에 역추적을 하면 된다.
|
|
""" |