[Level 3] 프로그래머스 - 스티커 모으기(2)

https://school.programmers.co.kr/learn/courses/30/lessons/12971

프로그래머스

풀이

• 원형으로 배열된 스티커에서 서로 인접한 스티커 2개를 동시에 뜯을 수 없다.
• 스티커를 뜯어서 점수를 얻는데, 최대로 얻을 수 있는 점수를 구하라

일반 스티커 문제에서는 그냥 DP로 풀면되는데, 이 문제는 원형 배열을 사용하는 문제이다.

즉, 첫 번째와 마지막 스티커가 서로 인접한다.

그래서 둘 중 하나만 고를 수 있다.

케이스를 나눠서 생각해야한다.

1. 케이스 1
   1. 첫번째 스티커를 선택하는 경우
      1. 이 경우 마지막 스티커는 절대 선택할 수 없다.
      2. 즉 사용 가능한 범위는 stickers[0] ~ stickers[n - 2]
2. 케이스 2
   1. 첫번쨰 스티커를 선택하지 않는 경우
      1. 이 경우 마지막 스티커도 선택 가능하다.
      2. 즉, 사용가능한 범위는 stickers[1] ~ stickers[n - 1]

각각을 DP를 사용해서 해결하면 된다.

DP 배열은 dp[i] = i번째 스티커 까지 고려했을 떄, 얻을 수 있는 최대 점수이다.

점화식을 생각하면 다음과 같이 구성 할 수 있다.

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

i번째 스티커를 안 뜯으면, 이전 최대 값을 유지하고, i번째 스티커를 뜯으면, 두 칸 전까지의 최대값 + 현재값을 더한다.

코드

def solution(sticker):
    answer = 0
    n = len(sticker)    
    if n == 1 :
        return sticker[0]
    
    def solve(dp_stickers) :
        dp = [0] * len(dp_stickers)
        dp[0] = dp_stickers[0]
        if len(dp_stickers) > 1 :
            dp[1] = max(dp_stickers[0], dp_stickers[1])
        for i in range(2, len(dp_stickers)) :
            dp[i] = max(dp[i - 1], dp[i - 2] + dp_stickers[i])
        return dp[-1]
    
    q1 = solve(sticker[:-1])
    q2 = solve(sticker[1:])
    answer = max(q1, q2)
    return answer