1463번: 1로 만들기

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n + 1)

for i in range(2,n+1):
  tmp = []
  
  if i % 3 == 0:
    tmp.append(dp[(i//3)])
  
  if i % 2 == 0:
    tmp.append(dp[i//2])
  
  tmp.append(dp[i - 1])
  dp[i] = min(tmp) + 1

print(dp[n])

n 을 입력 받고 연산 횟수의 최솟값을 넣을 dp 리스트를 만들어 0을 (n + 1)개 채워준다.
0들은 반복문을 통해 최솟값을 받아줄 것이다.
이때 0을 1개 더 추가하는 이유는 range out 을 피하기 위해서이다.

n 이 1일 경우 최솟값은 어짜피 0이기에 범위는 2부터 시작해 n 까지로 설정한다.

반복문 속에는 3으로 나누는 경우와 2로 나누는 경우 1을 뺄 경우를 tmp 리스트를 만들어 넣어준다.

만약 i % 3 == 0 이라면 dp[ i // 3 ]를 tmp에 저장
만약 i % 2 == 0 이라면 dp[ i // 2 ]를 tmp에 저장
그리고 1을 빼는 경우는 항상 가능하기 때문에 dp[ i - 1 ]을 tmp에 저장한다.

그러면 dp[ i ]는 위에 tmp 에 저장한 각 경우의 최솟값에서 연산 1회를 더 한 것이기 때문에 min(tmp) + 1을 저장해주면 된다.