[BOJ] 30460: 스위치(Python)

30460번: 스위치

문제 설명

t초에 스위치를 누르면 t, t+1, t+2초에 얻는 점수를 2배로 만들 수 있다. 얻을 수 있는 점수의 최댓값을 구해보자.

나의 풀이

import sys
input=sys.stdin.readline

def func():
    n=int(input())
    score=list(map(int,input().split()))+[0,0]
    dp=[0, score[0], score[0]+score[1]]

    for i in range(2, n+2):
        dp.append(max(dp[-1]+score[i], dp[-3]+(score[i-2]+score[i-1]+score[i])*2))

    return dp[-1]

print(func())

dp[i]를 i초 시점까지의 최대 점수라고 하면, 현재 선택할 수 있는 경우의 수는 버튼을 누르지 않는 경우와 3초 전에 버튼을 누른 경우로 나눌 수 있다. 둘 중 더 큰 점수를 선택해서 저장하면 된다.

시간복잡도

for문에서 O(n)이 걸린다.