li[n] 에는 li[n - 1], li[n / 3], li[n /2]의 최솟값 + 1의 값을 넣어줬다.
다 채워진 li 에서 입력된 li[n - 1], li[n / 3], li[n /2] 중에서 최솟값을 갖는 index를 다시 n으로 설정하였음
근데 계속 메모리 초과가 나길래
int(input()) => int(sys.stdin.readline())
list => array 로 바꿔주었더니 해결되었다....!
import sys
from array import array
n = int(sys.stdin.readline())
li = array('i', [0] * (n + 3))
li[1] = 0
li[2] = 1
li[3] = 1
result = []
for i in range(4, n + 1):
if i % 6 == 0:
li[i] = min(li[i - 1], li[i // 3], li[i // 2]) + 1
elif i % 3 == 0:
li[i] = min(li[i - 1], li[i // 3]) + 1
elif i % 2 == 0:
li[i] = min(li[i - 1], li[i // 2]) + 1
else:
li[i] = li[i - 1] + 1
print(li[n])
while n > 1:
if n % 6 == 0:
if li[n - 1] <= li[n // 3] and li[n - 1] <= li[n // 2]:
result.append(n)
n -= 1
elif li[n // 3] <= li[n - 1] and li[n // 3] <= li[n // 2]:
result.append(n)
n //= 3
elif li[n // 2] <= li[n - 1] and li[n // 2] <= li[n // 3]:
result.append(n)
n //= 2
elif n % 3 == 0:
if li[n - 1] <= li[n // 3]:
result.append(n)
n -= 1
else:
result.append(n)
n //= 3
elif n % 2 == 0:
if li[n - 1] <= li[n // 2]:
result.append(n)
n -= 1
else:
result.append(n)
n //= 2
else:
result.append(n)
n -= 1
result.append(1)
print(*result)