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

 

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

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

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

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

예시 이미지

나의 풀이

- DP 문제에서 하나의 DP만으로 해결하려고 했다.

- 그러나 그럴 경우 원형 배열의 특수성 때문에 생기는 문제를 해결하지 못했고 예를 들어 2번째부터 짝수로 더해질 때였다.

- 이 문제는 시작점을 얻고 시작하면 끝점을 못얻고 끝점을 얻으면 시작점을 못얻는다는 점을 이용해 문제를 쪼갠다.

- 그렇게 DP를 두 개를 쓰게 된다.

- DP 문제는 풀면 풀수록 어려운 문제는 DP를 여러개 쓰도록 만든다는 점을 배우는 것 같고 분할해서 생각하는게 중요하다는 점을 배워가는 것 같다.

def solution(money):
    # 문제의 요지는 인접한 두 집을 털지 않으면서 최대한으로 훔치는 방법
    # 최대값 문제이므로 그리디, 탐색, DP
    # 모든 집과 집이 연결되어 있어 경로가 너무 많아지므로 탐색은 아니다
    # 처음부터 돌며 돈이 많은 집부터 가면 될 수 있으므로 그리디가 가능성 있어보인다.
    # 그러나 문제는 내가 최대라고 해서 갔는데 결국 총합은 더 낮을 수도 있다.
    # 따라서 항상 최선의 경우를 고려하는 것이 아닌 모든 경우에서의 탐색이 필요하니 완전탐색
    # 백만이라는 수를 돌기 위해서는 DP 필요
    # 핵심은 앞과 맨 뒤가 연결되어 있는 걸 고려해야한다는 것
    
    dp1 = [0 for i in range(len(money)+1)]
    dp2 = [0 for i in range(len(money)+1)]
    
    dp1[1] = money[0]
    dp1[2] = max(money[0], money[1])
    dp2[2] = money[1]
    dp2[3] = max(money[1], money[2])
    
    for i, ele in enumerate(money[2:-1], start=3):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i-1])
            
    for i, ele in enumerate(money[3:], start=4):
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i-1])
            
    return max(dp1[-2], dp2[-1])