📌 백준 1463번 - 1로 만들기 (DP)

✨ 문제 요약

정수 N이 주어졌을 때, 아래 연산 중 하나를 선택해서
정수 1을 만들기 위한 최소 연산 횟수를 구하는 문제입니다.

사용할 수 있는 연산

X → X / 3 (단, 3으로 나누어떨어질 때)
X → X / 2 (단, 2로 나누어떨어질 때)
X → X - 1

🧠 초기 접근 시도 (그리디 → 실패)

처음에는 아래처럼 단순하게 나눌 수 있을 때마다 나누는 식으로 접근했지만,

while N > 1:
    if N % 3 == 0:
        N //= 3
    elif N % 2 == 0:
        N //= 2
    else:
        N -= 1

이 방식은 항상 최적의 해를 보장하지 않습니다.
예를 들어 N = 10일 때,
그리디 방식은 10 → 5 → 4 → 2 → 1 (4번)
최적은 10 → 9 → 3 → 1 (3번)

→ DP(동적 계획법)을 적용해야 최적해를 구할 수 있습니다.

🔧 점화식 설계

dp[i] = 정수 i를 1로 만들기 위한 최소 연산 횟수

dp[i] = min(
    dp[i - 1] + 1,              # -1 연산
    dp[i // 2] + 1 (if i % 2),  # /2 연산
    dp[i // 3] + 1 (if i % 3)   # /3 연산
)

i는 항상 i-1에서 올 수 있고, 조건에 따라 /2, /3에서도 올 수 있습니다.
따라서 가능한 모든 경로 중 최소값을 저장합니다.

🧱 DP 테이블 구성 (1차 테이블)

i	dp[i]	의미	선택 경로
1	0	1은 연산 필요 없음	-
2	1	2 → 1	i-1
3	1	3 → 1	i//3
4	2	4 → 2 → 1	i//2
5	3	5 → 4 → 2 → 1	i-1
6	2	6 → 3 → 1	i//3
7	3	7 → 6 → 3 → 1	i-1
8	3	8 → 4 → 2 → 1	i//2
9	2	9 → 3 → 1	i//3
10	3	10 → 9 → 3 → 1	i-1

🧪 DP 갱신 근거 (2차 테이블)

i	dp[i-1]+1	dp[i//2]+1	dp[i//3]+1	dp[i]	선택 경로
2	1	1	-	1	i-1
3	2	-	1	1	i//3
4	2	2	-	2	i-1
5	3	-	-	3	i-1
6	4	2	2	2	i//3
7	3	-	-	3	i-1
8	4	3	-	3	i//2
9	4	-	2	2	i//3
10	3	-	-	3	i-1

❌ 내가 처음 작성한 코드의 문제점

dp = [0] * N         # ❌ 크기 부족 → N+1로 수정 필요
dp[2] = 1
dp[3] = 1
for i in range(4, N+1):
    dp[i] = min(
        dp[i//3]+1 if i % 3 == 0,
        dp[i//2]+1 if i % 2 == 0,
        dp[i] - 1                # ❌ 아직 정의되지 않은 값 사용
    )

문제점 요약:

dp 크기 부족 → N+1 필요
dp[i]는 아직 정의되지 않았는데 dp[i] - 1을 사용함
연산 경로 중 무조건 존재하는 -1 연산(dp[i-1]+1)이 빠져 있음

✅ 수정된 정답 코드

N = int(input())
dp = [0] * (N + 1)

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

print(dp[N])

🧩 배운 점

DP 테이블을 만들 땐 항상 의미와 상태 정의부터 시작하자
dp[i]를 채울 때는 이전 상태들을 기반으로 점화식을 세운다
초기값 설정, 배열 크기, 값 정의 순서 등은 실수하기 쉬우니 주의!
1차 테이블 + 2차 테이블을 활용하면 디버깅도 쉽고 논리 흐름도 명확해진다

🎓 정리

항목	설명
문제 유형	DP (최소 연산 횟수)
점화식	`dp[i] = min(dp[i-1]+1, dp[i//2]+1, dp[i//3]+1)`
테이블	1차 테이블: 상태/의미 중심, 2차 테이블: 경로 비교 중심
디버깅 팁	테이블로 연산 흐름 추적하면 실수 줄일 수 있음

📘 같은 유형으로 연습하면 좋은 문제

백준 9095 (1,2,3 더하기)
백준 2579 (계단 오르기)
백준 11726 (2xn 타일링)