2579 계단오르기와 다르게, 0이 있으므로해서
0을 취하는 경우 바로뒤에 큰 수가 오는 경우 이를 취하지 못한다.
그렇다고 0을 입력받은 것에서 지우는 것은 안된다. 0이 있기 때문에 0바로 전의 max에서 0후의 값을 취할 수 있도록 되어 있기 때문.
ㄴ> 따라서 미포함 또한 DP의 영역안에 포함해서 점화식을 세워야 한다.
S5에서 0을 미포함하는 케이스가 있어야 하는데 이게 없다.
S8에서는 S5만을 보는데, S5는 0을 반드시 포함한 케이스이다.
ㄴ> 연속으로 k개를 취할 수 없는경우에 0처럼 오히려 손해가 되는 케이스가 있는 유형 생각할 것.
반례
8
1
2
3
4
0
0
100
1000
1107 > 1108나와야함
구현
import sys
R = [0]
n = int(input())
for _ in range(n):
R.append(int(sys.stdin.readline().strip()))
S = [[0,0,0] for __ in range(n+1)]
S[1][0] = R[1]
S[1][1] = R[1]
if n>=2:
S[2][0] = R[1] + R[2] #n=1일때 예외처리해야한다
S[2][1] = R[2]
S[2][2] = R[1]
for j in range(3,n+1):
S[j][0] = S[j-1][1] + R[j]
S[j][1] = S[j-1][2] + R[j]
S[j][2] = max(S[j-1])
mmax = -1
for ii in range(n+1):
for o in range(2):
if S[ii][o] > mmax:
mmax = S[ii][o]
print(mmax)
[0] : Rn + Rn-1(연속된) 값을 가진다.
[1] : Rn을 포함하되, Rn-1은 포함하지 않는다.(불연속)
[2] : Rn을 포함하지 않는 최대치
DP관점에서는 포함/미포함으로 가는 것 또한 좋은 접근으로 보임