프로그래머스 lv3 스티커모으기

출처

https://school.programmers.co.kr/learn/courses/30/lessons/12971

풀이

# 카드의 길이가 최대 100000이므로 직접 모은 경우의수를 구해보기엔 힘들다
def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]

    # 첫번째 스티커를 붙이느냐 안붙이느냐로 경우를 나누어서 DP로 구한다.
    dp = [0 for _ in range(len(sticker))]  # use first sticker
    dp2 = [0 for _ in range(len(sticker))]  # unused first sticker

    dp[0] = dp[1] = sticker[0]
    dp2[0], dp2[1] = 0, sticker[1]

    # dp[i-2]째까지 붙인 결과 + 스티커를 붙였을때 
    # 그런데 첫번째 스티커를 붙이면, 마지막것을 검사 못한다.
    for i in range(2, len(sticker) - 1):
        dp[i] = max(dp[i-2] + sticker[i], dp[i - 1])

    for i in range(2, len(sticker)):
        dp2[i] = max(dp2[i-2] + sticker[i], dp2[i - 1])

    return max(dp[-2], dp2[-1])