[Python/파이썬] Summer/Winter Coding(~2018) 스티커 모으기(2)

프로그래머스

코드

def solution(sticker):
    answer = 0
    if len(sticker) == 1:
        return sticker[0]
    # Case1) 0번 뜯음
    dp = [0 for _ in range(len(sticker))]
    dp[0], dp[1] = sticker[0], sticker[0] 
    for i in range(2, len(sticker)-1):
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
    answer = dp[-2]
    # Case2) 1번 뜯음(0번 못 뜯음)
    dp.clear()
    dp = [0 for _ in range(len(sticker))]
    dp[0], dp[1] = 0, sticker[1] 
    for i in range(2, len(sticker)):
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
    return max(answer, dp[-1])

처음에는 DFS로 하면 되지 않을까? 싶었는데 문제의 조건에서 스티커 배열의 길이가 최대 100,000이라 해서 바로 그 생각 버렸다. 

그리고 떠오른게 다이나믹 프로그래밍이었다. 점화식을 세워서 풀 수 있는 문제인거 같아서 생각해보니 본인 차례에서 선택할 수 있는 선택지는 본인 2개 이전의 스티커를 뜯고 본인도 뜯느냐, 아니면 본인 바로 이전의 스티커를 뜯고 본인은 못 뜯느냐 2가지뿐이다. 따라서 점화식은 다음과 같다.

dp[i] = max(dp[i-2] + sticker[i], dp[i-1])

그런데 이 때 주의할 점은 이 스티커는 원형으로 연결되어 있다. 하지만 주어진 배열은 1차원 배열이므로 0번 스티커를 뜯느냐, 1번 스티커를 뜯느냐 2가지 경우로 나누어서 풀이하였다. 

1. 0번 스티커를 뜯는경우, 1번 스티커를 못 뜯으므로 dp[1]에도 sticker[0]의 값을 저장해주고 시작하면 된다. 그리고 마지막 스티커(n-1)는 뜯을 수 없을 것이므로 dp[-2]가 0번 스티커를 뜯을 경우의 최대값이다.
2. 1번 스티커를 뜯는 경우, 0번 스티커는 못 뜯으므로 dp[0]에는 0을 저장해주고 시작한다. 이 경우는 마지막 스티커를 뜯을 수 있으므로 dp[-1]이 최대값이다.

정답은 이 두 경우 중 큰 값을 출력해주면 된다.