[백준 1463 파이썬] 1로 만들기

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

# 1로 만들기

x = int(input()) # 수 입력받기
dp = [0] * (x + 1) 

for i in range(2, x + 1): # 2부터 x까지 반복
    dp[i] = dp[i - 1] + 1 # 1을 빼는 연산 -> 1회 진행
    
    if i % 2 == 0: # 2로 나누어 떨어질 때, dp[i // 2] + 1 (2로 나누는 연산)
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0: # 3으로 나누어 떨어질 때, dp[i // 3] + 1 (3으로 나누는 연산)
        dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[x])

dp[i] = dp[i - 1] + 1 로 1을 빼는 연산을 먼저 한다.
2로 나누어 떨어지면 1을 빼는 연산과 2로 나누어 떨어질 때(dp[i // 2] + 1)를 비교해 최소값을 구한다.
3으로 나누어 떨어지면 1을 빼는 연산과 3으로 나누어 떨어질 때(dp[i // 3] + 1)를 비교해 최소값을 구한다.

2와 3으로 나누는 연산을 할 때 elif로 처리하면 안된다. 2로 나누는 연산과 3으로 나누는 연산 중 어떤게 더 효율적인지 비교해야하기 때문이다.