[BOJ] 1로 만들기 2

---

코드

import sys
input = sys.stdin.readline

n = int(input())
d = [[]] * (n + 1)
d[1].append(1)

for i in range(2, n + 1):
    d[i] = d[i - 1] + [i]
    if i % 3 == 0:
        if len(d[i]) > len(d[i // 3]) + 1:
            d[i] = d[i // 3] + [i]
    if i % 2 == 0:
        if len(d[i]) > len(d[i // 2]) + 1:
            d[i] = d[i // 2] + [i]

print(len(d[n])-1)
print(' '.join(map(str, reversed(d[n]))))

결과

풀이 방법

• 다이나믹 프로그래밍 문제이다.
• dp[i]에 i를 최소횟수로 연산하여 1로 만드는 방법(수열)을 저장하도록 하였다.
• 먼저 1을 빼는 연산을 하기 위해 d[i-1]에 i를 추가한 수열을 d[i]에 저장한다.
• i가 3으로 나누어 떨어지면, d[i//3]에 i를 추가한 수열의 길이가 d[i]의 길이보다 작은지(연산횟수가 적은지) 확인해보고 맞다면 d[i//3]에 i를 추가한 수열을 d[i]에 갱신한다.
• i가 2로 나누어 떨어지면, d[i//2]에 i를 추가한 수열의 길이가 d[i]의 길이보다 작은지(연산횟수가 적은지) 확인해보고 맞다면 d[i//2]에 i를 추가한 수열을 d[i]에 갱신한다.
• 최종적으로 구하는 답안은 d[n]에 저장된 수열을 뒤집어서 출력한 결과가 된다.

---