백준 12852. 1로 만들기2

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

12852번: 1로 만들기 2

'''
2or3으로 나눠떨어지면 2or3으로 나눔
1을 뺌
최소 연산 횟수
1로 만드는 과정 공백으로 구분해서 순서대로 출력
'''
n = int(input())

dp = [0] * (n+1) # 각 숫자까지의 최소 연산 횟수 저장
prev = [0] * (n+1) # 직전 숫자들 저장(경로 추적용)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 # 1을 뺀 경우가 기본값
    prev[i] = i - 1

    if i % 2 == 0 and dp[i//2] + 1 < dp[i]: # 2의 배수고, 현재의 최소 연산 횟수보다 작으면 갱신
        dp[i] = dp[i//2] + 1
        prev[i] = i // 2

    if i % 3 == 0 and dp[i//3] + 1 < dp[i]: # 3의 배수고, 현재의 최소 연산 횟수보다 작으면 갱신
        dp[i] = dp[i//3] + 1
        prev[i] = i // 3

print(dp[n]) # n까지의 최소 연산 횟수 출력

# 경로 복원
path = []
while n:
    path.append(n)
    n = prev[n]
print(*path)

다른 풀이들과 비교해봤을 때 메모리는 적게 차지하지만 속도는 느린 편인 것 같다...

위에서 기본적으로 전 숫자에서 1을 뺀 경우를 기본값으로 설정하는 이유가 무엇인가?

-> 모든 자연수에 대해 1을 빼는 연산은 항상 가능! -> 최소 한 가지 유효한 연산을 갖고 시작

-> 2나 3으로 나누어 떨어지지 않을 경우 따로 처리할 것 없이 되니까 간단해지는 것