DP_#PRO42897 : 도둑질

문제 설명

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

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

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

제한사항

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

 

 

---

인접한 집을 털면 경보가 울림
→ [1, 2, 3, 1] 에서 idx 0과 idx -1은 인접함
→ 첫번째 집을 털 경우와 첫번째 집을 털지 않을 경우로 분리

dp[i] 값
→ (i-2)번째 집을 털고 현재 i번째 집을 터는경우 (dp[i-2] + money[i])
→ (i-1)번째 집을 턴 경우(i번째 집 못텀) (dp[i-1])

 

def solution(money):
    """
    Args:
        money (List[int]) : 집에 있는 돈이 담긴 배열
    Returns:
        훔칠 수 있는 돈의 최댓값
    """
    # 첫번째 집을 터는 경우
    dp_1 = [0] * len(money)
    dp_1[0] = money[0]
    
    for i in range(1, len(money)-1):
    	dp_1[i] = max(dp_1[i-1], dp_1[i-2]+money[i])
    
    # 첫번째 집을 안터는 경우
    dp_2 = [0] * len(money)
    
    for i in range(1, len(money)):
    	dp_2[i] = max(dp_2[i-1], dp_2[i-2]+money[i])
    
    return max(dp_1[-2], dp_2[-1])