title: "[프로그래머스] 스티커 모으기(2) Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/12971"
description: "프로그래머스 Level 3 문제 [스티커 모으기(2)]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

def solution(sticker):
    # DP로 해결하되, 마지막 인덱스 예외 처리를 잘 해주면 될 듯
    # dp[0][i] = 0번째 스티커를 뜯고, i번째 스티커를 뜯은 상황에서
    # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수
    # dp[1][i] = 0번째 스티커를 뜯고, i번째 스티커를 뜯지 않은 상황에서
    # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수
    # dp[2][i] = 0번째 스티커를 뜯지 않고, i번째 스티커를 뜯은 상황에서
    # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수
    # dp[3][i] = 0번째 스티커를 뜯지 않고, i번째 스티커를 뜯지 않은 상황에서
    # 0~i번째 스티커를 가지고 만들 수 있는 최대 점수
    
    # 초기화
    # dp[0][0] = sticker[0]
    # dp[1][0] = 0 <-- 정의되지 않음
    # dp[2][0] = 0 <-- 정의되지 않음
    # dp[3][0] = 0
    
    # 점화식
    # dp[0][i] = dp[1][i-1] + sticker[i]
    # dp[1][i] = max(dp[0][i-1], dp[1][i-1])
    # dp[2][i] = max(dp[2][i-2], dp[3][i-1]) + sticker[i]
    # dp[3][i] = max(dp[2][i-2], dp[3][i-1])
    
    # 마지막 인덱스
    # dp[0][last] = 0  <-- 불가능함
    # dp[1][last] = max(dp[0][last-1], dp[1][last-1])
    # dp[2][last] = max(dp[2][last-2], dp[3][last-1]) + sticker[last]
    # dp[3][last] = max(dp[2][last-2], dp[3][last-1])
    
    dp = [[0] * 100001 for _ in range(4)]
    dp[0][0] = sticker[0]
    
    for i in range(1, len(sticker)):
        if i != len(sticker) - 1:
            
            if i != 1: # 예외) 0, 1번째를 모두 뜯을 수는 없습니다.
            	dp[0][i] = max(dp[0][i-2], dp[1][i-1]) + sticker[i]
                
            dp[1][i] = max(dp[0][i-1], dp[1][i-1])
            dp[2][i] = max(dp[2][i-2], dp[3][i-1]) + sticker[i]
            dp[3][i] = max(dp[2][i-1], dp[3][i-1])
        else: # 예외) 마지막 번째와 0번째를 모두 뜯을 수는 없습니다.
            dp[0][i] = 0
            dp[1][i] = max(dp[0][i-1], dp[1][i-1])
            dp[2][i] = max(dp[2][i-2], dp[3][i-1]) + sticker[i]
            dp[3][i] = max(dp[2][i-1], dp[3][i-1])
        
    return max(dp[i][len(sticker) - 1] for i in range(4))

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges