[Python/DP] 도둑질

문제 

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

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

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

 

제한사항

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

 

입출력 예

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

 

---

풀이

계단 오르기 문제와 유사하게 i 단계가 인접한 i-1, i+1 단계에 가지 못하는 유형의 문제이다.
dp[i]는 i번째 집을 방문할 때 도둑이 훔칠 수 있는 돈의 값이다. 

추가적으로 고려해야 할 점은 첫번째 인덱스와 마지막 인덱스의 집도 인접한 집이라는 것이다.
따라서, max(dp[i])가 도둑이 훔칠 수 있는 돈의 최댓값이다. 마지막 인덱스가 최댓값이 아니다.
첫번째 집을 방문하고 마지막 집을 방문하지 않는 경우, 첫번째 집을 방문하지 않고 마지막 집을 방문하는 경우를 나눠서 dp의 값을 구한다. 

'''
인접한 두 집을 털면 경보 울림

money : 각 집에 있는 돈이 담긴 배열
도둑이 훔칠 수 있는 돈의 최댓값을 return

첫 접근법:
OXOX
OXXO 집이 짝수 개인 경우 X 연달아
OXOXO
이거 아님!! 첫번째 집과 마지막 집은 이웃임 -> 어떻게 처리?

DP인지도 몰랐다

1. 원형이 아닌 일자 형태일 경우
dp[i] = max(dp[i-2] + money[i], dp[i-1])

2. 여기서 맨 앞을 털 떄, 맨 뒤를 털 때 나눠서
'''

def solution(money):
    answer = 0
    tmp = -float('inf')
    
    # 1. 첫 집을 무조건 터는 경우
    dp = [0]*(len(money))
    dp[0] = money[0] 
    dp[1] = dp[0]
    for i in range(2, len(money)-1):
        dp[i] =  max(dp[i-2] + money[i], dp[i-1])
    #print(dp) #[1, 2, 4, 0]
        
    # 2. 마지막 집을 무조건 터는 경우
    dp2 = [0]*(len(money))
    dp2[0] = 0
    dp2[1] = money[1] # 첫 집은 방문 안함
    for i in range(2, len(money)):
        dp2[i] =  max(dp2[i-2] + money[i], dp2[i-1])
    #print(dp2) #[0, 2, 3, 3]
    
    return max(max(dp), max(dp2))

헷갈려서는 안되는 부분이 첫 집을 털 수 있는 경우에서 max(dp)를 찾는 것이지(첫 집을 털 지 않는 게 최대일 수도 있다) 반드시 첫 집이나 마지막 집이 포함된다는 의미는 아니다.

참고