[ Lv 3 ] [ DP ] 스티커 모으기

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

코딩테스트 연습 - 스티커 모으기(2)

 

---

풀이 과정

---

1. 원형으로 연결되어 있으므로 첫번째 스티커를 선택하는지 선택하지 않는지에 따라 달라진다.
   1. 첫번째 스티커를 선택하는 경우, 마지막 스티커는 선택하지 않아야 함
   2. 첫번째 스티커를 선택하지 않는 경우, 마지막 스티커를 선택할 수도 있음
2. 첫번째를 선택하거나 선택하지 않은 각각의 경우에 따라 dp테이블을 구성해 준다.
3. 점화식은 다음과 같다.
   1. DP[i][0] = max(DP[i-1][0], DP[i-1][1])
   2. DP[i][1] = DP[i-1][0] + i번째 스티커
4. 첫번째 스티커를 선택한 경우는 마지막 스티커를 선택할 수 없으므로 DP[n-2]에서의 최댓값을, 첫번째 스티커를 선택하지 않은 경우는 마지막 스티커를 선택 가능하므로 DP[n-1]에서의 최댓값을 구해주면 된다.

---

소스 코드

---

def solution(sticker):
    answer = 0
    dp = [[0] * 2 for _ in range(len(sticker))]
    
    if len(sticker) == 1:
        return sticker[0]
    
    # 첫번째 선택
    dp[0][0], dp[0][1] = 0, sticker[0]
    dp[1][0], dp[1][1] = sticker[0], 0
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-2]))
    
    # 첫번째 선택하지 않은 경우
    dp[0][0], dp[0][1] = 0, 0
    dp[1][0], dp[1][1] = 0, sticker[1]
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-1]))
    
    return answer