[프로그래머스 LV 3] 스티커 모으기 (파이썬/python)

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

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

 

재귀 돌려서 완전탐색으로 풀었는데 시간초과가 퍼퍼퍼퍼펑 터져버린다.

LV3 부터는 더이상 잔재주가 통하지 않는다는걸 느꼈음.... 좀 더 효율적인 풀이법을 생각해보자

 

완전탐색으로 실패했고 dp로 견적이 나온다는 생각이 들었다.

바텀업으로 생각을 해보면

i번째 스티커를 뽑았을 경우 i-1번쨰는 뽑을 수 없고 i-2번째는 뽑거나 안 뽑거나 의 경우가 있다.

 

점화식을 세워보면 dp[i] = max( dp[i-2]+sticker[i] , dp[i-1] )

 

첫 번쨰 스티커를 뽑으면 마지막 인덱스 스티커를 뽑을 수 없고

첫 번쨰 스티커를 뽑지 않으면 마지막 인덱스 스티커를 뽑을 수 있다

그래서 2가지 상황을 전부 고려해줘야한다.

 

 

def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]
    # dp[i] = max(dp[i-2]+sticker[i],dp[i-1])
    dp = [0 for _ in range(len(sticker))]
 
    # 첫 번째 스티커를 고른경우
    # 마지막 인덱스는 확인하지 않아야한다.
    dp[0] = sticker[0]
    dp[1] = sticker[0]
    for i in range(2, len(sticker) - 1):
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1])
    value = max(dp)
 
    # 첫 번쨰 스티커를 고르지 않은경우
    # 마지막 인덱스는 확인 안해!
    dp = [0 for _ in range(len(sticker))]
    dp[1] = sticker[1]
    for i in range(2, len(sticker)):
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1])
 
    return max(value, max(dp))