[프로그래머스] 도둑질 (Python)

link 🔗 https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

 

def solution(money):
    dp1 = [0]*len(money)
    # 첫번째 집 털기
    dp1[0] = money[0]
    dp1[1] = money[0]
    for idx in range(2, len(money)-1):
        dp1[idx] = max(dp1[idx-1], dp1[idx-2]+money[idx])
    # 마지막 집 털기
    dp2 = [0]*len(money)
    dp2[1] = money[1]
    for idx in range(2, len(money)):
        dp2[idx] = max(dp2[idx-1], dp2[idx-2]+money[idx])
    answer = max(max(dp1), max(dp2))
    return answer

 

✏️ 메모

• 인덱스 0과 인덱스 -1은 원형으로 뒀을 때 서로 인접
• 첫번째 집을 무조건 터는 경우와 마지막 집을 무조건 터는 경우를 따로 생각했다.