[프로그래머스] 도둑질 (python 파이썬)

문제

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

코딩테스트 연습 - 도둑질

 

 

풀이 및 소스코드

연속된 부분은 더할 수 없기때문에

dp[i] = max(dp[i-1], dp[i-2]+money[i]) 라는 점화식이 나온다.

def solution(money):
    answer = 0
    dp1 = [0 for _ in range(len(money))]
    dp2 = [0 for _ in range(len(money))]

    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1]) #마지막 집을 털지 않기때문에 첫번째, 두번째 집 중 큰 집을 털면 된다.
    dp2[0] = 0 #마지막 집을 터는 경우 첫번째 집을 털 수 없기 때문에 0으로 초기화.
    dp2[1] = money[1]
    for i in range(2, len(money)-1): #마지막 집을 털지 않는 경우(첫번째 집을 털 수 있다.)
        dp1[i] = max(dp1[i-1], dp1[i-2]+money[i])
    for i in range(2, len(money)): #마지막 집을 터는 경우(첫번째 집을 털면 안된다.)
        dp2[i] = max(dp2[i-1], dp2[i-2]+money[i])
    answer = max(max(dp1), max(dp2))
    return answer