도둑질

프로그래머스

• 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.
• 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
• 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.
• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력

money	return
[1, 2, 3, 1]	4

---

접근 방식

: dp이용.
인접한 것을 함께 털지 못하기 때문에, dp[i-1], dp[i-2]+현재 중 max값을 현재 dp에 저장하면 된다.
원형이기 때문에 첫번째 원소와 마지막 원소도 인접한데 이는 어떻게 처리할까?

알게된 점

첫번째 집을 무조건 터는 경우와 털지 않는 경우로 나눈다.

• 첫번째 집을 무조건 터는 경우 - 마지막 집은 무조건 털지 못한다.
• 첫번째 집을 안터는 경우 - 마지막 집은 털 수도 있고 안털수도 있다.
  
  -> 두 경우 중 최댓값을 리턴하면 된다.

코드

def solution(money):
    n = len(money)
    dpA = [0]*n
    dpB = [0]*n
    
    # 첫번째o, 마지막은 털 수x
    dpA[0] = money[0]
    dpA[1] = money[0]
    for i in range(2, n-1):
        dpA[i] = max(dpA[i-1], dpA[i-2]+money[i])
    dpA[-1] = dpA[-2]
    
    # 첫번째x, 마지막은 털 수도 있고 안 털수도 있고
    dpB[0] = 0
    dpB[1] = money[1]
    for i in range(2, n):
        dpB[i] = max(dpB[i-1], dpB[i-2]+money[i])
    
    # 두 경우 중 최댓값
    return max(dpA[-1], dpB[-1])