====== 도둑질 ======
  * [[ps:problems:programmers:12971|스티커 모으기(2)]]과 동일한 문제이다

===== 풀이 =====
  * 원형이 아니라 직선으로 배열되어 있다면 아주 평범한 1차원 DP가 된다. 
    * dp[i]을 i번째 집까지에서 훔칠수 있는 최대 액수라 하면,
      * dp[i] = max(i번째 집에서 안훔치는 경우, i번째 집에서 훔치는 경우) = max(dp[i-1], dp[i-2] + money[i]) 
    * 으로 쉽게 정리된다
  * 이 문제에서는 원형이라서, 첫번째 집을 털었을 경우에는 마지막 집을 털수 없다는 조건이 추가되어 약간 복잡해진다.
    * 마지막 집을 안털거나, 첫번째 집을 안털거나, 두가지 경우로 나누어서 각각 최대값을 구한 뒤, 다시 그 둘 중에서 최대값을 구하면 된다.
    * 구현하는 방법은, 첫번째 집을 털었을 때와 안털었을 때로 나누어 두개의 dp 테이블을 만들어 계산한다.
      * dp1[i] 은 i번째 집까지에서 훔칠 수 있는 최대 액수이다
      * dp2[i] 은 첫번째 집을 털지 않고서 i번째 집까지에서 훔칠 수 있는 최대 액수이다
    * 이렇게 두면, 최종적으로 구하는 값은 마지막 집을 안턴 dp1[n-1]과, 첫번째 집을 안턴 dp2[n]중 최대값이 된다.
  * dp식이 이전 2항에 대한 점화식이므로, 슬라이딩 윈도우를 써서 공간복잡도 O(1)에 구현할 수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "Programmers 42897. 도둑질".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42897
- Solution link: http://www.teferi.net/ps/problems/programmers/42897
"""

def solution(money):
    dp1, dp1_cur = [0, money[0]], max(money[0], money[1])
    dp2, dp2_cur = [0, 0], money[1]
    for m in money[2:]:
        dp1[-1], dp1[-2] = dp1_cur, dp1[-1]
        dp2[-1], dp2[-2] = dp2_cur, dp2[-1]
        dp1_cur = max(dp1[-1], dp1[-2] + m)
        dp2_cur = max(dp2[-1], dp2[-2] + m)
    return max(dp1[-1], dp2_cur)

</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_4}}