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