[프로그래머스 Programmers][Python] 도둑질

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

코딩테스트 연습 - 도둑질 | 프로그래머스

이 문제는 솔직히 몰라서 copy-driven-dev를 실천했다.

 

DP 문제인데, 집이 원형이므로 첫번째 집을 털면 자동으로 마지막 집은 못 턴다. 원형이므로 마지막이다.

 

dp 배열을 두개를 만드는데,

• dp1 배열 : 첫번째 집을 털었다. 길이는 len(money) -1 마지막 집은 못 턴다
• dp2 배열 : 첫 번째 집을 못 털었다.길이는 len(money)  마지막 집 털 수 있다.

이제 DP를 수행하는데 선택지는 다음과 같다.

1. 지금 집을 털 경우 : 2번째 전 집 (집을 털면 집 앞뒤의 방범장치가 울리므로) + 지금 집
2. 지금 집을 안 턴다: 1번째 전 집 털이 수확을 그대로 챙김

 

이제 dp1, dp2를 전부 수행한 것 중에 큰 쪽을 선택한다.

 

이렇게 배열 나누는 문제를 백준에서도 본적 있는데, 아마 집 페인트 색칠 문제였던 것 같다.

 

def solution(money):

    dp1 = [0] *(len(money)-1) 
    dp2 = [0] *len(money) 
    dp1[0],dp1[1] = money[0],money[0]

    dp2[0] , dp2[1] = 0,money[1]

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

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


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