[알고리즘] 프로그래머스 - 스티커 모으기(2)

프로그래머스 - 스티커 모으기(2)

다른 사람 풀이

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

    dp = [[0]*len(sticker) for _ in range(2)]
    dp[0][0] = 0 # dp[0][i] = 첫 번째 스티커를 안뜯었을 때 i번째까지 최대값
    dp[1][0] = sticker[0]

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

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

원형이라고 해서 복잡하게 생각했는데, 그냥 2차원 dp를 선언하여 첫 번째 스티커를 때는 경우와 때지 않는 경우로 구분해서 생각하면 된다.