DP - 도둑질(Lv.4)

• 도둑 문제 유형(인접한 집은 동시에 X)은 해당 집 털거나 안털거나!
  -> 점화식: dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
  -> dp[i - 1]: 이번 집 안털고 이전까지 최댓값 유지
  -> dp[i - 2] + money[i]: 이번 집 털고, 전전 집까지의 최대값 더하기
• 원형인 경우 2가지 케이스로 나눠 풀기:
  1) 첫 집 터는 경우 -> 마지막 집 털 수 없음
  2) 첫 집 안터는 경우 -> 마지막 집 털 수 있음

def solution(money):
    answer = -1
    m_len = len(money)
    
    # 1) 첫 집 털기 -> 마지막 집 못털음 ----
    money_1 = money[:m_len - 1]
    
    dp = [0] * (m_len) # dp[i] : i번째 집까지 털었을 때의 최대 수익
    dp[1] = money_1[0]
    
    for i in range(2, len(money_1) + 1):
        # 현재 집 i를 터는 경우와 안털고 직전 수익 이어받는 경우 중 큰 경우 채택
        dp[i] = max(money_1[i - 1] + dp[i - 2], dp[i - 1])
    
    max_1 = max(dp)
    
    
    # 2) 첫 집 안털기 -> 마지막 집 털 수 있음 ----
    money_2 = money[1:]
    
    dp = [0] * (m_len)
    dp[1] = money_2[0]
    
    for i in range(2, len(money_2) + 1):
        dp[i] = max(money_2[i - 1] + dp[i - 2], dp[i - 1])
    
    max_2 = max(dp)
    
    answer = max(max_1, max_2)

    return answer