[파이썬] 프로그래머스 : 스티커 모으기 2 (Lv.3)

[파이썬] 프로그래머스 : 스티커 모으기 2 (Lv.3)

프로그래머스

---

풀이

방향성 생각

• 첫 스티커를 선택하면 마지막 스티커를 선택하지 못한다. 첫 스티커 선택 유무에 따라 2가지로 나뉨
• dp[스티커 선택 유무][스티커 위치]

전체코드

def solution(sticker):
    
    n = len(sticker)
    if n<3:
        return max(sticker[:2])

    dp = [[0]*n for _ in range(2)] # dp[처음 스티커 선택 유무][위치]

    dp[0][:2] = [0,sticker[1]]
    dp[1][:2] = [sticker[0],max(sticker[:2])]
    
    for state in range(2):
        for stage in range(n-2):
            dp[state][stage+2] = max(dp[state][stage+1], dp[state][stage] + sticker[stage+2])

    return max(dp[0][-1],dp[1][-2])

• n<3인 경우 둘중에 큰거 하나 고르면 된다.
• 처음 선택 안하면 0, 처음 선택 안하고 다음거는 sticker[1]
• 처음 선택하면 sticker[0], 처음 선택하면 2번째에는 sticker[0]이랑 처음 선택 안하고 두 번째거 선택한 stciker[1] 중 최대값 선택
• dp[처음 선택 안한거 중][마지막], dp[처음 선택 한거][마지막-1]
• dp[1][-1]은 불가능한 값이라 고려 x

코멘트

.