[Baekjoon/Python] 1463번: 1로 만들기 - 효과는 굉장했다!

1463번: 1로 만들기

 

알고리즘 분류

• 다이나믹 프로그래밍

 

 

SOLUTION

import sys

N = int(sys.stdin.readline())
dp = [0 for _ in range(N+1)] 

for i in range(2, N+1):
    dp[i] = dp[i-1] + 1 # 1을 빼는 경우 일 때
    
    if i % 2 == 0 and dp[i] > dp[i//2] + 1: # 2로 나누어 떨어지면 2로 나눈 수 에서 횟수 + 1 
        dp[i] = dp[i//2] + 1

    if i % 3 == 0 and dp[i] > dp[i//3] + 1: # 3으로 나누어 떨어지면 3으로 나눈 수 에서 횟수 + 1
        dp[i] = dp[i//3] + 1

print(dp[N])