문제 설명

전체 코드

def solution(sticker):
    answer = 0
    if len(sticker) == 1:
        return sticker[0]

    dp = [0 for _ in range(len(sticker))]
    dp2 = [0 for _ in range(len(sticker))]

    dp[0] = sticker[0]
    dp[1] = sticker[0]

    dp2[0] = 0
    dp2[1] = sticker[1]

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

    value_1 = max(dp)

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

    value_2 = max(dp2)

    answer = max(value_1, value_2)
    return answer

해결 방법

동적프로그래밍을 사용하는 문제로 맨 앞의 스티커를 사용한다고 가정하는 dp변수를 선언해준다. 이 변수는 첫번째 스티커를 사용했으므로 dp[0] = sticker[0]를 해주며 두번째 스티커는 사용하지 않았으므로 dp[0]과 같은 dp[1] = sticker[0]이다. 이제 dp[2]부터는 dp[i] = max(dp[i-1](i번째 스티커를 사용하지 않은 최대값), dp[i-2] + sticker[i](i번째 스티커를 사용한 값))이 된다.

dp2는 반대로 첫번째 스티커를 사용하지 않고 두번째 스티커부터 사용한 경우이다. 이 두 배열중 가장 높은 값인 max(value_1, value_2)가 정답이다.