[프로그래머스] 도둑질

문제

[프로그래머스] 도둑질

풀이

• dp[i] : i번째 집까지 털었을 때, 최댓값

• 전 집을 털었을 때, 현재 집은 털지 못하므로 dp[i]는 바로 전 집까지 털 수 있는 최댓값 혹은전전집까지 털었을 때 최댓값 + 현재 집의 money 중 큰 값.

그 결과 점화식은,
dp[i] = max(dp[i-1], dp[i-2]+money[i])

1번 집과 마지막 집은 이어져 있으므로, 1번 집을 털 때와 1번을 안 털 때 두 경우로 나눠서 진행하고, 두 경우 중 최댓값을 리턴한다.

• 1번 집을 털 때 : 마지막 집은 털지 못함. 1번부터 마지막-1번째 집까지 계산
• 1번 집을 안 털 때 : 2번부터 마지막 집 까지 계산

정답 코드

def solution(money):
    answer = 0
    dp1 = [0 for i in range(len(money))] # 첫 번째 집을 터는 경우
    dp2 = [0 for i in range(len(money))] # 첫 번째 집 안 터는 경우
    
    dp1[0] = money[0] 
    for i in range(1, len(money)-1): # 마지막-1번째 집까지
        dp1[i] = max(dp1[i-1], dp1[i-2]+money[i])
    
    dp2[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])