[Python][파이썬][프로그래머스] 도둑질(동적계획법)

문제 설명

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

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

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

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

money                                                                      return

[1, 2, 3, 1]

4

---

▶ 문제 설명

1. 만약 i번째 집을 털려고 할때 가능한 경우는 다음과 같다.

• 이미 i-1번째 집을 털었을 때 : i번째 집을 털 수 없다. 즉 i까지의 합계는 i-1번째 집을 털었을 때까지 합계이다.
• i-1집을 털지 않았을 경우 : i번째 집을 털 수 있다. 즉 i까지의 합계는 i-2번째 집을 털었을 때까지 합계와 i를 털었을때의 합계이다.
• 따라서 다음과 같은 재귀식이 완성된다.
• table[i] 가 money[i]번째까지 턴 금액이라 가정한다면,  table[i] = max(table[i-1], table[i-2] + money[i]) 이다.

2. 한편, 집들이 동그랗게 배치되어있기 때문에 첫집과 마지막집은 인접하며, 첫집과 마지막집을 같이 털 수 없으므로, 첫집을 털 때와 마지막집을 털 때의 경우를 나누어야 한다.

 

▶ 코드 풀이

def solution(money):
    result = []
    # 첫 집을 털경우
    table = [0 for i in range(len(money))] 
    table[0] = money[0]
    table[1] = money[0]
    for i in range(2, len(money)-1):
        table[i] = max(table[i-1], table[i-2] + money[i])
    result.append(max(table))
    
    # 마지막 집을 털 경우
    table = [0 for i in range(len(money))]
    table[1] = money[1]
    for i in range(2, len(money)):
        table[i] = max(table[i-1], table[i-2] + money[i])
    result.append(max(table))
    
    return(max(result))