📌난이도🥈3

이거맞나..?

📌코드

import sys
N = int(input())
s = [int(sys.stdin.readline()) for _ in range(N)]

d = [0]*N

if N == 1:
    d[0] = s[0]
elif N == 2:
    d[0] = s[0]
    d[1] = max(s[0]+s[1], s[1])
else:
    d[0] = s[0]
    d[1] = max(s[0]+s[1], s[1])
    d[2] = max(s[0]+s[2], s[1]+s[2])

    if N > 3:
        for i in range(3, N):
            d[i] = max(d[i-2]+s[i], d[i-3]+s[i-1]+s[i])

print(d[N-1])

마지막 위치를 무조건 밟아야한다고 했으므로 이를 d[ i ] 라고 표현하자.
(최근 까지 푼 dp 문제들에서 i 인덱스 까지의 합(최대 , 최소) 으로 표현하는 문제들이 많았다.
o x o
o x o o

무조건 밟아야하는 위치가 i 라 했을때 i 위치의 최댓값 d[ i ]는 다음과 같이 표현될 수 있음
d[i] = d[i-2] + s[i]
d[i] = d[i-3] + s[i-1] + s[i]

무조건 밟는 i 위치 기준 2가지 경우의 수가 나올 수 있다.
위 조건을 점화식으로 쓰기 위해서는 i 가 3일때 i-3이 존재해야하므로 d 배열은 2번 인덱스 까지 값이 존재해야한다.

• i = 0 일때
  d[0] = s[0]
  
  
• i = 1 일때
  d[1] = max( s[0] + s[1] , s[1] )
  
  
• i = 2 일때
  d[2] = max (s[0] + s[2] , s[1] + s[2] )
  
  

📌후기

점화식 이용하는 dp 문제 매우 약하다. 이번 문제는 세번째 겹치면 안된다는 조건에 너무 빠져있어서 오래걸렸다. 점화식 형태를 보는 연습이 꾸준히 필요할 것 같다

그리고 인덱스 에러 엄청 나던데!!!!!!!!!!!!!!!!!!!!!!!!!!! N = 1 , N = 2 를 신경안쓰고 있었다...