동적계획법 ( Dynamic Programming) - 도둑질** (Lv.3)

문제 설명

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

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

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

 

제한사항

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

입출력 예

Money	Return
[1, 2, 3, 1]	4

 

Key Point - 앞집을 털게 되면, 현재 집은 털지 못하게 되고, 만약 앞집을 털지 않았으면 현재 집을 털 수 있다.

 

즉, 도둑이 훔칠 수 있는 돈의 최댓값을 저장하는 dp 테이블을 생성하고, dp[i]는 1번부터 i번째 집까지 털었을 때 훔칠 수 있는 돈의 최댓값이다.

 

dp[i]는 바로 전 집까지 훔칠 수 있는 최댓값와 전전집까지의 훔칠 수 있는 최댓값 + 현재 집의 money 두 가지 경우로 나뉘어진다.

 

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

def solution(money): 
    dp1 = [0] * len(money) 
    dp2 = [0] * len(money) 
    #첫번째 집을 터는 경우
    dp1[0] = money[0] 
    for i in range(1, len(money) - 1): 
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i]) 
    #첫번째 집을 털지 않는 경우
    dp1[0] = 0  
    for i in range(1, len(money)): 
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i]) 
        
    return max(dp1[-2], dp2[-1])