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

도둑질

문제 링크

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

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한 사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

문제 풀이

문제의 핵심은 첫번째 집의 돈을 챙기면 마지막 집의 돈을 못 챙긴다는 사실이다. 해당 사실을 유의하며 2가지 경우를 들어 해당 경우 중 최대값을 출력한다.

def solution(money):
    n = len(money)

    dp1 = [0] * n
    dp1[0] = money[0]
    dp1[1] = money[0]
    for i in range(2, n-1): 
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])

    dp2 = [0] * n
    dp2[0] = 0  
    dp2[1] = money[1]
    for i in range(2, n): 
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i])

    return max(dp1[-2], dp2[-1])