[Programmers] Q12971 스티커 모으기 (2)

[BOJ] Q12971 스티커 모으기 (2)

Question

Language: Python

Difficulty: Gold 4~5

원형으로 이루어진 배열에 있을떄, 하나를 선택할 경우 양옆의 원소는 선택할 수 없다. 이렇게 될때는 첫번쨰 index을 뽑은 경우 마지막 index을 뽑을 수 없다.

따라서, 첫번째 index을 뽑는 경우와 첫번째 index을 선택하지 않는 경우 나눠서 생각해야한다.

가령, [1,2,3,4,5,6,7,8]과 같은 원형큐가 있을 때, 첫번째 index를 뽑는 경우 [1,2,3,4,5,6,7]을 확인하면 되고, 첫번째 index를 뽑지 않는 경우, [2,3,4,5,6,7,8]을 고려한다.

첫번째 index를 뽑는 경우

dp[0]=sticker[0]
#첫번째 index를 선택하는 경우, 두번째 index를 선택할 수 없다.
dp[1]=sticker[0]
#마지막 index는 선택할 수 없다.
for i in range(n-1):
    dp[i]=max(dp[i-1],dp[i-2]+sticker[i])

첫번째 index를 뽑지 않는 경우

dp[0]=0
dp[1]=sticker[1]
#마지막 index도 고려할 수 있다.
for i in range(2,n):
    dp[i]=max(dp[i-1],dp[i-2]+sticker[i])

Solution

def solution(sticker):
    answer = 0
    n=len(sticker)
    if n==1:
        return sticker[0]
    dp=[0]*(n+1)
    #첫번째 index을 뽑는 경우
    dp[0]=sticker[0]
    dp[1]=sticker[0]
    
    for i in range(1,n-1):
        dp[i]=max(dp[i-1],dp[i-2]+sticker[i])
    answer=max(dp)
    
    dp=[0]*(n+1)
    
    #첫번째 index을 뽑지 않는 경우
    dp[0]=0
    dp[1]=sticker[1]
    
    for i in range(1,n):
        dp[i]=max(dp[i-1],dp[i-2]+sticker[i])
    answer=max(answer,max(dp))

    return answer