[Python | 파이썬] 도둑질 (프로그래머스 DYNAMIC PROGRAMMING)

[Python | 파이썬] 도둑질 (프로그래머스 DYNAMIC PROGRAMMING)

 

 

원형으로 이어진 집들 중에서 이어진 두 집은 연속으로 털 수 없다. 따라서 첫번째 집을 터는 경우에는 마지막 집을 털 수 없다. 첫번째 집을 터는 경우는 따라서 n-1번째 집까지만 확인해야한다. 그리고 첫번째 집을 털지 않는 경우에는 dp[0] = 0이어야 한다. 마지막 집을 털어도 되기 때문에 n번째 집까지 확인한다.

 

def solution(money):
    answer = 0
    n = len(money)
    dp_1, dp_2 = [0 for _ in range(n-1)], [0 for _ in range(n)]
    dp_1[0] = money[0]
    dp_1[1] = max(money[0], money[1])
    for i in range(2, n-1):
        dp_1[i] = max(dp_1[i-1], dp_1[i-2]+money[i])
    dp_2[1] = money[1]
    for i in range(2, n):
        dp_2[i] = max(dp_2[i-1], dp_2[i-2]+money[i])
    answer = max(dp_1[n-2], dp_2[n-1])
    return answer

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

프로그래머스