title: "[프로그래머스] 도둑질 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/42897"
description: "프로그래머스 Level 4 문제 [도둑질]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

def solution(money):
    # 스티커 모으기(2) 문제와 동일한 것 같다. 원형 dp
    
    dp = [[0] * 1000001 for _ in range(4)]
    dp[0][0] = money[0]
    
    for i in range(1, len(money)):
        if i != len(money) - 1:
            
            if i != 1: # 예외) 0, 1번째를 모두 훔칠 수는 없습니다.
            	dp[0][i] = max(dp[0][i-2], dp[1][i-1]) + money[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]) + money[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]) + money[i]
            dp[3][i] = max(dp[2][i-1], dp[3][i-1])
        
    return max(dp[i][len(money) - 1] for i in range(4))

출처

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