2579:계단오르기

https://www.acmicpc.net/problem/2579

풀이

1. d[i]

   • a[i]를 밟았을 경우, 0~i 번째까지 최대 점수

2. d[i]

   • max( a[i]+a[i-1]+d[i-3] , a[i]+d[i-2] )

3. example : 10 20 15 25 10 20

   • 20 X 15 O 25 O : a[i]+a[i-1]+d[i-3]
   • 15 X 25 O : a[i]+d[i-2]

4. 근데, 여기서 사소한 문제 !

   • n을 입력받고, 배열을 생성할 때
     0n-1 인덱스로 할 것이냐,
     1n 인덱스로 할 것이냐에 따라 문제가 생김

5. 0~n-1 인덱스로 다음과 같이 하면 틀렸음.

   • 왜냐하면, d[2]를 구하지 않았기 때문.

6. 따라서 다음과 같이 d[2]를 구해야함

7. 1~n 인덱스로 범위 잡으면, 상관 없음