2156 - DP

nhwang·2022년 7월 6일
0

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관점에서는 포함/미포함으로 가는 것 또한 좋은 접근으로 보임

profile
42Seoul

0개의 댓글