프로그래머스 lv3 스티커모으기
출처
https://school.programmers.co.kr/learn/courses/30/lessons/12971
풀이
# 카드의 길이가 최대 100000이므로 직접 모은 경우의수를 구해보기엔 힘들다
def solution(sticker):
if len(sticker) == 1:
return sticker[0]
# 첫번째 스티커를 붙이느냐 안붙이느냐로 경우를 나누어서 DP로 구한다.
dp = [0 for _ in range(len(sticker))] # use first sticker
dp2 = [0 for _ in range(len(sticker))] # unused first sticker
dp[0] = dp[1] = sticker[0]
dp2[0], dp2[1] = 0, sticker[1]
# dp[i-2]째까지 붙인 결과 + 스티커를 붙였을때
# 그런데 첫번째 스티커를 붙이면, 마지막것을 검사 못한다.
for i in range(2, len(sticker) - 1):
dp[i] = max(dp[i-2] + sticker[i], dp[i - 1])
for i in range(2, len(sticker)):
dp2[i] = max(dp2[i-2] + sticker[i], dp2[i - 1])
return max(dp[-2], dp2[-1])
Leave a comment