✅ DP

문제

링크

1. 문제 접근 및 해결 로직

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.

즉, $n$층에 오를 수 있는 경우는 $n-2$층에서
1. 한칸씩 두번 오르는 경우
2. 두칸을 한번에 오르는 경우
두가지이다.

$f(n)$ 은 각 계단에 쓰여 있는 점수가 주어질 때 얻을 수 있는 총 점수의 최댓값 라고 할때
$f(n)$은 $n-2$ 에서 한칸씩 두번 오르는 경우와 두칸을 한번에 오르는 경우 두가지이므로 $n-1$ 계단을 거치고 온 경우와 거치지 않고 온 경우라고 볼 수 있다.
따라서 $f(n)$ 은 $f(n-1)$와 $f(n-2)$ 를 더한 값이다

• 정의
  $f(n)$ : 각 계단에 쓰여 있는 점수가 주어질 때 얻을 수 있는 총 점수의 최댓값
  $stair[n]$ : $n$층 계단의 점수
• 구하는 답
  $f(n)$
• 초기값
  $f(0)=0$
  $f(1)=stair[1]$
  $f(2)=max(stair[1]+stair[1], stair[2])$
• 점화식
  $f(n)=f(n-1)+f(n-2)$

2. 코드

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항