📌 문제 요약

• 문제 이름: 1463번: 1로 만들기
• 알고리즘 분류: 다이나믹 프로그래밍 (DP)
• 사용 언어: Python 3

정수 $N$이 주어졌을 때, 1) 3으로 나누거나, 2) 2로 나누거나, 3) 1을 빼는 세 가지 연산을 적절히 사용하여 1을 만들려고 합니다. 이때 연산을 사용하는 횟수의 최솟값을 구하는 문제입니다.

---

💡 문제 접근 방법 (핵심 로직)

이 문제는 그리디(Greedy) 알고리즘처럼 무조건 큰 수(3)로 먼저 나눈다고 해서 최적해가 보장되지 않습니다. (예를 들어 10의 경우, $10 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1$ (4번) 보다 $10 \rightarrow 9 \rightarrow 3 \rightarrow 1$ (3번)이 더 빠릅니다.)

따라서 모든 경우의 수를 효율적으로 탐색하기 위해, 작은 수부터 결과를 저장해 나가는 다이나믹 프로그래밍(DP)의 바텀업(Bottom-Up) 방식을 사용해야 합니다.

어떤 수 $i$를 1로 만드는 최소 연산 횟수는 다음 세 가지 경우 중 가장 작은 값이 됩니다.
1. dp[i - 1] (1을 뺐을 때의 최소 횟수) + 1번(현재 연산)
2. dp[i // 2] (2로 나누었을 때의 최소 횟수) + 1번(현재 연산)
3. dp[i // 3] (3으로 나누었을 때의 최소 횟수) + 1번(현재 연산)

이를 코드로 구현할 때, -1을 하는 경우를 먼저 dp[i]에 담아둔 뒤, 2로 나누어떨어질 때와 3으로 나누어떨어질 때 min() 함수를 사용하여 횟수를 갱신해 나갑니다.

---

💻 코드 구현

import sys
input = sys.stdin.readline

N = int(input())

# DP 테이블 0으로 초기화 (N+1 크기)
dp = [0] * (N + 1)

def DP(n):
    for i in range(2, n + 1):
        # 1을 빼는 경우를 베이스로 설정
        dp[i] = dp[i-1] + 1
        
        # 2로 나누어 떨어지면, 이전 값과 비교하여 최솟값 갱신
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)
        
        # 3으로 나누어 떨어지면, 이전 값과 비교하여 최솟값 갱신
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)

DP(N)
print(dp[N])

---

🚨 트러블 슈팅 및 회고

• elif 대신 if 사용의 중요성: 코드를 짤 때 if i % 3 == 0 이후에 elif i % 2 == 0을 사용하면 큰일납니다. 6처럼 2와 3의 공배수인 숫자가 들어왔을 때, 3으로 나누는 것과 2로 나누는 것 중 어느 쪽이 나중에 더 이득일지 모르기 때문에 반드시 각각 독립적인 if문으로 두 경우를 모두 탐색하여 min()으로 최솟값을 걸러내야 한다는 논리적 포인트를 확실히 짚고 넘어갔습니다.
• Top-Down vs Bottom-Up: 재귀를 이용한 탑다운(Top-Down) 방식으로도 풀 수 있지만, 파이썬의 경우 최대 입력값인 $N = 10^6$이 들어오면 RecursionError가 발생할 위험이 있습니다. 따라서 반복문을 이용해 작은 문제부터 안전하게 쌓아 올라가는 바텀업(Bottom-Up) 방식이 메모리와 시간 제약 면에서 훨씬 안정적인 접근임을 배웠습니다.