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

https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

# 5단계 문제라서 손을 안대고 있었는데, 내가 생각했던 '5단계'의 난이도는 아니었다..

 

# 16~20줄에서 dp테이블을 갱신하는 원리는 다음과 같다.

  i번째 집을 털 때 최댓값(dp[i])은 아래 두가지 케이스 중 큰 값이다.

     1. (i-2)번째 집을 털고 현재 i번째 집을 터는경우 (dp[i-2] + money[i])

     2. i번째 집을 턴 경우(현재 i번째 집을 털지 못한다) (dp[i-1])

 

따라서 dp[i]= max(dp[i-2] + money[i], dp[i-1]) 이다.

 

def solution(money):
    answer = 0
    n = len(money)
    # dp1: 첫번째 집을 털었을 경우 (마지막 집을 털지 못함)
    # dp2: 첫번째 집을 털지 않았을 경우(마지막 집 털 수 있음)
    dp1 = [0] * n
    dp2 = [0] * n
    # dp1은 "무조건" 첫번째 집을 터는 경우 이므로 dp1[0]과 dp1[1]에 money[0]을 넣어준다.
    # (첫번째 집을 털었으므로 두 번째 집은 털지 못하므로 dp1[1]도 money[0]이다.)
    dp1[0] = dp1[1] = money[0]
    # dp2는 첫번째 집을 털지 않으므로 dp2[0]에 그대로 0을 넣어주고 dp2[1]에는 money[1]
    # dp2[2]에 money[1]과 money[2] 중 큰 값을 넣어준다.
    dp2[1] = money[1]
    dp2[2] = max(money[1], money[2])
    # dp1은 마지막 집을 털지 못하므로 반복문을 n-2까지만 돌리면서 dp테이블을 갱신해준다 
    for i in range(2, n - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])
    # dp2는 마지막 집을 털 수 있으므로 반복문을 n-1까지 돌린다.
    for i in range(2, n):
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])

    # dp1의 최댓값과 dp2의 최댓값 중 큰 값을 return해준다.    
    return max(dp1[n - 2], dp2[n - 1])

(프로그래머스 level: 5)