문제 설명

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

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

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

제한 사항

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

정답 코드

def solution(sticker):
    answer = 0

    # dp[i]=x 의 의미: i 인덱스에 도달하기 전 까지 최댓값 x
    dp_first=[0]*len(sticker)
    dp_second=[0]*len(sticker)
    
    dp_first[0]=sticker[0]
    # 첫 번째 것을 선택할 경우
    for i in range(1,len(sticker)):
        # 바로 다음 것은 첫 번째 또는 두 번째 중 가장 큰 것 고름
        if i==1:
            dp_first[i]=max(dp_first[0],sticker[1])
        # 마지막 것은 선택 불가    
        elif i==len(sticker)-1:
            dp_first[i]=max(dp_first[i-1],sticker[i])
        # 그 외의 것은 이전 인덱스를 선택하지 않았냐와 선택했냐로 나눈다. 선택하지 않았다면 i-2 번째 값과 합산하고, 선택했다면 바로 이전 값인 i-1 번째 값을 가져온다. 그리고 그 중 큰 것을 택한다.
        else:
            dp_first[i]=max(dp_first[i-2]+sticker[i],dp_first[i-1])
    
    # 스티커 길이가 1인 경우 예외 처리
    if len(sticker)==1:
        return dp_first[-1]
    
    dp_second[1]=sticker[1]
    # 두 번째를 고를 경우, 첫 번째는 선택하지 않음
    for i in range(2,len(sticker)):
        if i==2:
            dp_second[i]=max(dp_second[i-1],sticker[i])
        else:
            dp_second[i]=max(dp_second[i-2]+sticker[i],dp_second[i-1])
    
    return max(dp_first[-1],dp_second[-1])

dp 냄새가 나서 이차원 배열 dp로 풀어보려 했었다. 하지만 시간 초과가 났었다.

그런데 참고 링크 설명을 보니 일차원 배열 dp만으로도 풀수 있음을 알게 되었다.

특히 dp[i]=x 의 의미가 i 인덱스에 도달하기 전 까지 최댓값 x 라는 것을 이용해서 푼게 놀랍다.

참고

https://small-stap.tistory.com/m/60