DP를 연습해 보자!!

DP 어디에 사용할까?

상황	해결하려는 문제
같은 계산을 여러 번 반복하는 문제	중복되는 계산을 피해서 속도 향상
조합 가능한 경우의 수가 많아지면서 폭발하는 문제	하위 문제의 결과를 저장해서 시간 단축
최적의 선택(최댓값, 최솟값, 최대합, 최소횟수 등)	모든 경우를 일일이 계산하지 않고, 점화식을 기반으로 최적해 도출

---

예제: "계단 오르기"

계단이 n칸 있다. 한 번에 1칸 또는 2칸 오를 수 있다. 꼭대기까지 오르는 방법의 수는?

이 문제를 보고 피보나치 수열을 떠올렸다. 재귀로 구현했었는데 당연히 이것도 재귀였다.. 이 문제를 푸는 방법은 다음과 같다.

Case 1: 마지막 점프가 1칸이었다

그 말은… 내가 마지막 점프 전에는 3번 칸에 있었다는 뜻이야.

즉, 3번 칸까지 도달하는 모든 경로에 마지막으로 1칸을 추가하면
4번 칸에 도달하는 새로운 경로가 되는 거야!

예시:

• 3까지 도달하는 경로:
  [1,1,1], [1,2], [2,1] → 총 3가지

• 각각의 경로에 +1칸 추가:

  • [1,1,1] → [1,1,1,1]
  • [1,2] → [1,2,1]
  • [2,1] → [2,1,1]

이렇게 3개 → dp[3]개의 경로가 4로 도달함

---

Case 2: 마지막 점프가 2칸이었다

그 말은… 내가 마지막 점프 전에는 2번 칸에 있었다는 뜻!

즉, 2번 칸까지 가는 모든 경로에 마지막으로 2칸을 추가하면
4에 도달하는 새로운 경로가 만들어져.

예시:

• 2까지 도달하는 경로:
  [1,1], [2] → 총 2가지

• 각각에 +2칸 추가:

  • [1,1] → [1,1,2]
  • [2] → [2,2]

→ 또 2개 생김 → dp[2]

---

구현

앞에서 몇 칸을 얼마나 뛰든 상관없이 결국 n-1칸이나 n-2칸을 거쳐야 한다. 결국 n-1칸까지 가는 경우의 수와 n-2칸까지 가는 경우의 수를 계산해서 더해주면 n칸까지 가는 총 경우의 수가 얼마인지 구할 수 있다.

함수 climb_stairs(n):

  만약 n이 0이거나 1이면:
    → 방법은 한 가지밖에 없음 (그냥 그 칸에 서 있기)
    → 1을 반환

  크기 (n + 1)의 배열 dp를 만든다
  dp[0] = 1  // 0칸까지 오는 방법: 시작점
  dp[1] = 1  // 1칸까지 오는 방법: 1칸 오르기

  2부터 n까지 반복하면서:
    → 현재 칸까지 오는 방법은
      → 전 칸(dp[i-1])에서 1칸 오기
      → 전전 칸(dp[i-2])에서 2칸 오기
    → dp[i] = dp[i-1] + dp[i-2]

  반복이 끝난 후 dp[n]을 반환

부끄럽지만 gpt가 짜준 수도 코드를 참고했다.

def climb_stairs(n):
    dp = [0] * (n+1)

    if n <= 1:
        return 1
    
    dp[0] = 1
    dp[1] = 1

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

    return dp[n]


print(climb_stairs(4))

아직 구현까지 스스로 할 수 있는 실력은 안된다. 많은 노력이 필요할 것 같다.