프로그래머스 도둑질 (DP)

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

코딩테스트 연습 - 도둑질

DP문제이다.

 

인접한 집을 털게되면 경보음이 울게된다.

 

그래서 한집 띄어서 도둑이 털게 만들어야 한다.

 

현재 집의 돈의 금액과 [i-2]위치의 금액과의 합과 [i-1]에서의 도둑이 털수 있는 금액의 합을 비교해서 큰값을 가지면 된다.

def solution(money):
    
    if len(money) == 3:
        return max(money[0] , money[1] , money[2])
    
    dp1 = [0] * len(money)
    dp2 = [0] * len(money)
    
    dp1[0] = money[0]
    dp1[1] = max(money[0] , money[1])
    
    
    for i in range(2 , len(money)-1):
        dp1[i] = max(dp1[i-1] , money[i] + dp1[i-2])
    
    
    dp2[0] = 0
    dp2[1] = money[1]
    for i in range(2 , len(money)):
        dp2[i] = max(dp2[i-1] , money[i] + dp2[i-2])
        
        
    
    
    answer = max(max(dp1) , max(dp2))
    return answer