프로그래머스 도둑질 파이썬

프로그래머스 파이썬 도둑질 프로그래머스 도둑질 파이썬 파이썬 프로그래머스 도둑질 파이썬 도둑질 프로그래머스 도둑질 프로그래머스 파이썬 도둑질 파이썬 프로그래머스

도둑질

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

문제 단순화

• money 배열이 주어 진다.
• 해당 배열에서 연속된 값을 선택하지 않을 때, 선택된 값들의 최댓값을 리턴한다.

문제풀이

• 1차원 dp를 만든다.
• dp[i]를 결정할 때, i-1번째 값과 i-2번째 값이 필요하기 때문에, dp[0], dp[1]을 0으로 두어 계산한다.

    dp[i] = max(dp[i-1], dp[i-2] + money[i-2])

• 첫 번째 값과 마지막 값은 이어져 있기 때문에, 첫 번째 값을 선택했을 때, 마지막 값을 선택했을 때, 두 경우로 나누어 계산한다.

코드

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