[알고리즘][2] 도둑질

문제 설명
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

image.png

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항
이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.
입출력 예
money	return
[1, 2, 3, 1]	4

나의 풀이

- 처음과 끝을 분리할 수 있도록 dp를 2개 만들어주는게 핵심

def solution(money):
    # 최댓값이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수 없기 때문에 그리디 X
    # 집이 1,000,000개이면 탐색은 시간 초과남
    # 따라서 DP
    # 처음과 끝에 집도 연결되어 있는게 핵심
    
    dp1 = [0] * len(money)
    dp2 = [0] * len(money)
    
    dp1[0] = money[0]
    dp1[1] = max(dp1[0], money[1])
    dp2[0] = 0
    dp2[1] = money[1]
    dp2[2] = max(dp2[1], money[2])
    for i in range(2, len(money)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
        dp2[i+1] = max(dp2[i], dp2[i-1] + money[i+1])
    
    return max(dp1[len(money)-2], dp2[len(money)-1])

returnr값을 리팩토링한 코드

def solution(money):
    # 최댓값이므로 그리디, DP, 탐색
    # 항상 최선의 선택을 할 수 없기 때문에 그리디 X
    # 집이 1,000,000개이면 탐색은 시간 초과남
    # 따라서 DP
    # 처음과 끝에 집도 연결되어 있는게 핵심
    
    dp1 = [0] * len(money)
    dp2 = [0] * len(money)
    
    dp1[0] = money[0]
    dp1[1] = max(dp1[0], money[1])
    dp2[0] = 0
    dp2[1] = money[1]
    dp2[2] = max(dp2[1], money[2])
    for i in range(2, len(money)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])
        dp2[i+1] = max(dp2[i], dp2[i-1] + money[i+1])
    
    return max(dp1[-2], dp2[-1])