[Python] 백준 1463번 - 1로 만들기

문제 https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

DP 오랜만에 푸는 거라 정신 못 차렸다.

어떻게 풀어야 할 지 감이 안 잡혀서 알고리즘 분류 확인하고 디피 문제라는 걸 확인한 후에 풀었다.

디피 연습을 좀 해야할 것 같다.

간단한 코드 설명은 주석으로 적어놓았다.

 

import sys
input = sys.stdin.readline

n= int(input())
dp = [0 for _ in range(n+1)]

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1 #일단 1은 무조건 빼놓고 (연산 3)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1) #연산3의 결과와 연산1의 결과 비교
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1) #연산3의 결과와 연산2의 결과 비교

print(dp[n])