[프로그래머스][동적계획법] 도둑질

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

프로그래머스

문제 해결 아이디어

• 어차피 돈은 양수이기에 두칸씩 띄어서 선택하면 장땡이다
• 첫번째 집과 마지막집은 붙어있기에 동시에 선택을 못한다
• 둘중하나 선택을 안하면 직선처럼 문제를 생각할 수 있다
• 두케이스중 큰값을 골라준다

 

def solution(money):
    answer = 0
    # 마지막집을 선택하지 않은경우
    dp = [0] * len(money)
    dp[0] = money[0]
    dp[1] = max(money[0], money[1])
    for i in range(2, len(money) - 1):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
    answer = max(answer, max(dp))

    #첫번째 집을 선택하지 않은 경우
    dp = [0] * len(money)
    dp[0] = 0
    dp[1] = money[1]
    for i in range(2, len(money)):
        dp[i] = max(dp[i-2] + money[i], dp[i-1])
    answer = max(answer, max(dp))
    
    return answer