[BOJ] 1463 1로 만들기 - 파이썬

TIP

문제 링크 (opens new window)

문제 요약

정수에 사용할수있는 세가지 연산이 주어졌을때 정수 N 을 1로 만들기 위해 필요한 연산 횟수의 최솟값을 구하라

문제 풀이

• dp[i] : i 를 1로 만들기 위해 필요한 최소 연산 횟수
• 문제 자체가 점화식이다.

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    dp = [sys.maxsize]*(n+5)
    dp[1] = 0
    dp[2] = 1

    for i in range(3, n+1):
        dp[i] = min(dp[i//3]+i%3,
                    dp[i//2]+i%2,
                    dp[i-1]) + 1
    print(dp[n])

main()