프로그래머스 스티커 모으기(2)

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

이전의 계산결과를 이용하는 dp를 사용하는 문제이다.
N이 10만이라는 점에서 완전탐색이나 dfs등의 방법을 사용한다면 시간초과의 가능성이 매우 커보였다.
그렇기 때문에 dp를 이용해 이전의 구간합을 구해주는 것이 문제인데,
이전값을 선택했는지 안했는지에 따라 dp값의 선택이 달라지는 문제가 있었다.
그렇기 때문에 dp를 2개를 생성하고 첫번째를 넣은 dp, 안넣은 dp로 나누어 계산하였다.

def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]
    dp = [0 for _ in range(len(sticker))] ## 앞의 스티커를 사용했다고 가정
    value = 0
    dp[0] = sticker[0]
    dp[1] = dp[0]
    for i in range(2,len(sticker)-1):
        dp[i] = max(dp[i-2]+sticker[i], dp[i-1])
    value = max(dp)
    
    udp = [0 for _ in range(len(sticker))]
    udp[0] = 0
    udp[1] = sticker[1]
    for i in range(2,len(sticker)):
        udp[i] = max(udp[i-2]+sticker[i], udp[i-1])
    value2 = max(udp)
    
    return max(value,value2)

좋은 웹페이지 즐겨찾기