🧩 동적 프로그래밍 문제 접근법 완전 정리

점화식 구성 / 상태 정의 / 실전 예제로 익히기

---

✅ DP 문제에 접근하는 흐름

DP 문제를 만나면 무작정 코드를 짜기보다, 먼저 문제의 구조를 파악해야 한다.

🔹 핵심 체크리스트

1. 작은 문제로 쪼갤 수 있는가?
2. 그 작은 문제들을 이용해 큰 문제를 만들 수 있는가?
3. 비슷한 연산을 반복하고 있는가? (중복 계산)
4. 입력 크기 N이 1,000~10,000 정도인가? (완전탐색 불가능)

---

✅ 점화식이란?

점화식(Recurrence Relation)이란, 현재 상태의 값을 이전 상태의 값들로 표현한 식이다.

DP는 결국 점화식을 코드로 구현하는 과정이다.

예시: 피보나치 수열

F(n) = F(n-1) + F(n-2)

→ 현재 항 = 이전 항 + 그 이전 항

---

✅ 상태(State)를 정의하는 법

🔹 DP에서 상태란?

"어떤 값을 구하고 있는가"를 수식으로 표현한 변수이다.

예를 들어,

• dp[i]: i번째까지 고려했을 때의 최솟값
• dp[i][j]: i번째까지 선택했을 때 j개의 항을 고른 경우의 합

✔️ 상태를 구체적으로 설명할 수 있어야 점화식이 자연스럽게 따라온다

---

✅ 실전 예제로 흐름 익히기

---

📌 예제 1: 피보나치 수열

입력: n
출력: F(n) = F(n-1) + F(n-2)

• 상태: dp[i] = i번째 피보나치 수
• 점화식: dp[i] = dp[i-1] + dp[i-2]
• 초기값: dp[0] = 0, dp[1] = 1

n = 10
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[n])

---

📌 예제 2: 1로 만들기 (백준 1463)

입력: 정수 X (1 <= X <= 10^6)
출력: 연산 최소 횟수 (X -> 1)
연산: 나누기 3, 나누기 2, 빼기 1

• 상태: dp[x] = x를 1로 만드는 데 필요한 최소 연산 횟수
• 점화식:

dp[x] = min(
  dp[x-1] + 1,
  dp[x//2] + 1 if x % 2 == 0,
  dp[x//3] + 1 if x % 3 == 0
)

• 초기값: dp[1] = 0

x = int(input())
dp = [0] * (x + 1)
for i in range(2, x + 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[x])

---

📌 예제 3: 계단 오르기 (백준 2579)

계단마다 점수 존재 / 마지막 계단은 반드시 밟아야 함
한 번에 1칸 or 2칸 / 연속 3칸 불가

• 상태: dp[i] = i번째 계단까지 올라갔을 때 최대 점수
• 점화식:

dp[i] = max(
  dp[i-2] + score[i],
  dp[i-3] + score[i-1] + score[i]
)

• 초기값: 문제 조건에 따라 dp[1], dp[2], dp[3] 수동 설정

---

✅ 실전 팁

• 항상 상태 정의 → 점화식 구성 → 초기값 설정 → 반복 구현 순서로 접근
• 상태가 2차원 이상일 수 있음 (dp[i][j])
• 문제에서 "최솟값, 최댓값, 방법의 수" 등이 나오면 DP 의심
• Top-down (재귀 + 메모이제이션)으로 먼저 설계하고 Bottom-up 전환도 가능

---

🎯 마무리 요약

• DP는 "상태 정의"와 "점화식 유도"가 핵심이다
• 문제에서 작은 문제로 쪼개고, 그것으로 큰 문제를 만들 수 있는지 먼저 판단하자
• 점화식이 떠오르면 절반은 푼 셈이다 💡