스티커 모으기(2)

def solution(sticker): # DP로 해결하되, 마지막 인덱스 예외 처리를 잘 해주면 될 듯 # dp[0][i] = 0번째 스티커를 뜯고, i번째 스티커를 뜯은 상황에서 # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수 # dp[1][i] = 0번째 스티커를 뜯고, i번째 스티커를 뜯지 않은 상황에서 # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수 # dp[2][i] = 0번째 스티커를 뜯지 않고, i번째 스티커를 뜯은 상황에서 # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수 # dp[3][i] = 0번째 스티커를 뜯지 않고, i번째 스티커를 뜯지 않은 상황에서 # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수 # 초기화 # dp[0][0] = sticker[0] # dp[1][0] = 0 <-- 정의되지 않음 # dp[2][0] = 0 <-- 정의되지 않음 # dp[3][0] = 0 # 점화식 # dp[0][i] = dp[1][i-1] + sticker[i] # dp[1][i] = max(dp[0][i-1], dp[1][i-1]) # dp[2][i] = max(dp[2][i-2], dp[3][i-1]) + sticker[i] # dp[3][i] = max(dp[2][i-2], dp[3][i-1]) # 마지막 인덱스 # dp[0][last] = 0 <-- 불가능함 # dp[1][last] = max(dp[0][last-1], dp[1][last-1]) # dp[2][last] = max(dp[2][last-2], dp[3][last-1]) + sticker[last] # dp[3][last] = max(dp[2][last-2], dp[3][last-1]) dp = [[0] * 100001 for _ in range(4)] dp[0][0] = sticker[0] for i in range(1, len(sticker)): if i != len(sticker) - 1: if i != 1: # 예외) 0, 1번째를 모두 뜯을 수는 없습니다. dp[0][i] = max(dp[0][i-2], dp[1][i-1]) + sticker[i] dp[1][i] = max(dp[0][i-1], dp[1][i-1]) dp[2][i] = max(dp[2][i-2], dp[3][i-1]) + sticker[i] dp[3][i] = max(dp[2][i-1], dp[3][i-1]) else: # 예외) 마지막 번째와 0번째를 모두 뜯을 수는 없습니다. dp[0][i] = 0 dp[1][i] = max(dp[0][i-1], dp[1][i-1]) dp[2][i] = max(dp[2][i-2], dp[3][i-1]) + sticker[i] dp[3][i] = max(dp[2][i-1], dp[3][i-1]) return max(dp[i][len(sticker) - 1] for i in range(4))