[파이썬] [DP] Pro 도둑질

문제

https://programmers.co.kr/learn/courses/30/lessons/42897?language=python3 

코딩테스트 연습 - 도둑질

 

코드

def solution(money):
    dp=[0]*(len(money))
    dp[0]=money[0]
    dp[1]=max(money[1],money[0])
    for i in range(2,len(money)-1):
        dp[i]=max(dp[i-1],dp[i-2]+money[i])

    dp1 = [0] * (len(money))
    dp1[0] = 0
    dp1[1] = money[1]
    for i in range(2, len(money)):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])

    answer=max(max(dp),max(dp1))

    return answer

생각 정리

첫 집과 마지막 집이 둘다 포함되는 경우가 생길 수 있기 때문에
1) 첫 번째 집을 무조건 털고, 마지막 집은 털지 않는 경우
2) 마지막 집을 무조건 털고 첫 번째 집은 털지 않는 경우
로 나눠서 생각해야 한다.