[Python] 백준 1463 1로 만들기

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

풀이

import sys

num = int(sys.stdin.readline().rstrip())

num_list = [0, 0, 1, 1]

for i in range(4, num + 1):
    num_list.append(num_list[i-1] + 1)
    
    if i % 2 == 0:
    	# 2로 나누어 떨어졌을 때의 경우 + 1을 해줘야 한다 ex) f(2) = 1일 때, f(4) 는 f(2)보다 
        # 한 번 더 연산(나누기)했기 때문에 1을 더해줘야 한다
        num_list[i] = min(num_list[i // 2] + 1, num_list[i])
    if i % 3 == 0:
        num_list[i] = min(num_list[i // 3] + 1, num_list[i])
    
print(num_list[num])