[Algorithm] programmers/kakao/2017summer/level4/스티커 모으기

문제 설명

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.
image
원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

접근법

>> 딱 봐도 dp 문제인데, recursive하게 접근했다가 시간만 버림
>> dp는 알면서도 모르겠다.
>> 다른 개발자님의 블로그를 탐색하여 참고하였다. 
>> https://velog.io/@skyepodium/programmers-%EC%8A%A4%ED%8B%B0%EC%BB%A4-%EB%AA%A8%EC%9C%BC%EA%B8%B0
>> 딱 보면 "아! 이렇게!" 이 정도 수준으로 이해되는 것을 넘어, 내가 직접 짤 수 있어야 한다.

>> dp[x]를 구해나가는 진행 방향은 from left to right
>> x 인덱스 스티커를 냅두거나 뜯었을 때 최대 기대값
>> 점화식으로 표현하면 
>> dp[x] = max(냅둠, 뜯음)
>> dp[x] = max(dp[x-1], dp[x-2] + sticker[x])

>> 우선 점화식에 x-2라는 표현이 있으니 위 식을 사용할 수 있는 {x|x > 1 and x < n}
>> 즉 dp[0], dp[1]이 결정되어 있어야 한다. initial state 결정은 다음과 같이 두 경우로 나뉜다.

    >> 0번째 스티커를 냅두는 경우
        >> dp[0] = 0, dp[1]= sticker[1]

    >> 0번째 스티커를 뜯는 경우
        >> dp[0] = sticker[0], dp[1] = dp[0]

>> 씨피피 코드 잘 참고 하였습니다. 감사합니다.

코드

def solution(sticker):
    n = len(sticker)
    if n < 4:
        return max(sticker)

    dp = [-1 for _ in range(n)]
    # first sticker peel off
    dp[0] = sticker[0]
    dp[1] = sticker[0]
    for i in range(2, n-1):
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
    answer = dp[n-2]

    # first sticker not peel off
    dp[0] = 0
    dp[1] = sticker[1]
    for i in range(2, n):
        dp[i] = max(dp[i-2] + sticker[i], dp[i-1])
    answer = max(answer, dp[n-1])
    return answer