[프로그래머스] 도둑질 - python

도둑질

문제 설명

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

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

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

제한사항

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

풀이

개미전사와 비슷한 문제

다만 원형으로 이어져있다는 점이 다르다.

인접한 집들은 고를 수 없으므로 n번째에서 고를 수 있는 경우의 수는 두가지이다.

• n-1만 선택하기
• n-2 와 n 선택하기

이를 점화식으로 나타내면

dp[i] = max(dp[i-1], dp[i-2] + money[i])

가 된다.

다만 첫 번째 집을 선택할 경우 마지막 집을 선택할 수 없고, 마지막 집을 선택할 경우 첫 번째 집을 선택할 수 없기 때문에 두 경우를 나눠서 생각해야 한다.

• 첫 번째 집을 무조건 선택하는 경우 (마지막 집은 선택할 수 없음)
• 첫 번째 집을 선택하지 않고 마지막 집을 선택하는 경우

def solution(money):
    n = len(money)
    dp1 = [0] * n
    # 첫 번째 집을 무조건 선택하는 경우
    dp1[0] = money[0]
    dp1[1] = max(dp1[0], dp1[1]) # 두 번째집을 선택할 수도 있고 안할 수 도 있다.
    
    for i in range(2, n - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])
    
    dp2 = [0] * n
    dp2[0] = 0
    dp2[1] = money[1]
    
    for i in range(2, n):
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])
​
    return max(max(dp1), max(dp2))