[코딩테스트 연습(Python)] 백준 1463번_1로 만들기(DP)

 

import sys

input = sys.stdin.readline

# dp는 연산 횟수의 최솟값 리스트
dp = [0] * 1000001
    
n = int(input())

# n이 1일 경우 아무런 연산할 필요 없이 연산 횟수는 0
# 따라서 2부터 시작
for i in range(2, n+1):
    
    # 1. 1을 빼는 경우
    dp[i] = dp[i-1] + 1
    
    # 2. 2로 나누는 경우
    if i % 2 == 0:
        # 1번 경우와 2번 경우를 비교하여 작은 값을 dp[i]에 담는다
        dp[i] = min(dp[i], dp[i//2] + 1)
    
    # 3. 3으로 나누는 경우
    if i % 3 == 0:
        # 위에서 구한 연산 횟수와 3번 연산을 비교하여 작은 값을 dp[i]에 담는다.
        dp[i] = min(dp[i], dp[i//3] + 1)

# 결과적으로 min 함수를 통해 1,2,3번 연산 횟수의 최솟값을 구하게 된다.

print(dp[n])