[프로그래머스/Python] 동적계획법(DP) - 도둑질

풀이

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])
        
    # 마지막 집을 무조건 터는 경우 = 첫번째 집을 털지 못함
    for i in range(1, len(money)):
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])
        
    # dp1 = [1, 2, 4, 0]
    # dp2 = [0, 2, 3, 3]
    return max(dp1[-2],dp2[-1])

• 첫 번째 집을 털면, 마지막 집을 털지 못한다는 것 <=> 첫 번째 집을 털지 않으면, 마지막 집을 털 수 있다.
• 집이 1개 있을 경우, 그 집을 터는 게 최댓값
• 집이 2개 있을 경우, 인접한 집을 털지 못하니까 두 집 중 Money가 큰 집을 터는 게 최댓값
• 집이 3개 있을 경우, i번째 집 money + i-2번째 집 money 혹은 i-1번째 집 money 중 더 큰 집을 터는 게 최댓값
• 점화식: dp[i] = max(dp[i-1], money[i] + dp[i-2])