문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

# 12852
import sys
input = lambda: sys.stdin.readline().strip()

# 1. if x % 3 == 0 -> x//3
# 2. if x % 2 == 0 -> x//2
# 3. x -= 1

n = int(input())
number = [0] * (n+1)

for i in range(2, n+1):
    if i % 2 == 0 and i % 3 == 0:
        number[i] = min(number[i//2], number[i//3], number[i-1]) + 1
    elif i % 2 == 0:
        number[i] = min(number[i//2], number[i-1]) + 1
    elif i % 3 == 0:
        number[i] = min(number[i//3], number[i-1]) + 1
    else:
        number[i] = number[i-1] + 1
        
cnt = number[n]-1
output = [n]
for i in range(n-1, 0, -1):
    if number[i] == cnt and (output[-1] == i*3 or output[-1] == i*2 or output[-1] == i+1):
        output.append(i)
        cnt -= 1
        
print(number[n])
print(*output)

백준 12852 1로 만들기 2