[프로그래머스] 스티커 모으기(2)- 파이썬

문제

---

• 프로그래머스 Summer/Winter Coding(~2018) 문제 링크

풀이

---

• 난이도 : level 3
• 예전 문제들은 이렇게 딱 기본 문제로 나온 것 같은데 요즘 추세는 장황한 문제가 나오는 편이다.
• DP로 풀었다.
• leet code에서도 비슷한 문제를 좀 더 깔끔하게 푼 풀이를 본 것 같은데 아래 코드는 그다지 깔끔하지는 않다.
• 원형이기 때문에 첫 번째를 포함하면 마지막 스티커를 포함할 수 없어 케이스를 나누어 계산하였다.
• dp_y는 포함케이스, dp_n는 불포함 케이스로 계산하여 풀어주었다.
• dp[idx]는 각 idx 까지의 최대값이다.
• idx 위치에서 스티커를 포함한다면 그 전단계를 포함하지 못하므로 idx -2 위치의 최대값을 포함, 그렇지 않다면 최대값은 idx -1 위치의 최대값이다.
• 마지막은 두 케이스 중 큰 값을 리턴한다.

코드

---

def solution(sticker):
    if len(sticker) <= 3 :
        return max(sticker)
    N = len(sticker)
    dp_y= [0 for _ in range(N-1)]
    dp_n= [0 for _ in range(N)]
    dp_y[0] = dp_y[1] = sticker[0]
    dp_n[0] = 0
    dp_n[1] = sticker[1]
    for i in range(2, N -1) :
        dp_y[i] = max(sticker[i] + dp_y[i-2], dp_y[i-1])
    for j in range(2, N) :
        dp_n[j] = max(sticker[j] + dp_n[j-2], dp_n[j-1])
    return max(dp_y[-1], dp_n[-1])