도둑질

• 스티커 모으기(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)에 구현할 수 있다.

"""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)