[알고리즘] Programmers 도둑질 #Python

[Programmers] 도둑질 바로가기

📍 문제 설명

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

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

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

---

📍 제한사항

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

---

📍 입출력 예

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

---

📍 풀이

💡 고찰

• 문제를 보자마자 [알고리즘] Programmers 스티커 모으기(2) #Python와 같은 유형의 문제임을 알 수 있었다.
• 원형 구조로 인접한 원소를 선택하지 못하는 경우에는 2가지 경우로 분리하여 생각해야 한다.
  • 첫 번째 원소를 선택하고 마지막 원소를 선택하지 않는 경우
  • 마지막 원소를 선택하고 첫 번재 원소를 선택하지 않는 경우
• 각 경우에 맞게 동적 프로그래밍(Dynamic Programming)을 적용하면 문제를 해결할 수 있다.

📌 문제 풀이

✏️ [1] 첫 번째 집을 털고 마지막 집을 털지 않은 경우

dp1 = [0] * N
dp1[0], dp1[1], dp1[2] = money[0], money[1], money[0] + money[2]
for i in range(3,N-1):
    dp1[i] = money[i] + max(dp1[i-2],dp1[i-3])

• dp1 배열의 첫 번째(0), 두 번째(1), 세 번째(2) 원소의 값을 초기화 한다.
• 네 번째(3) 집부터 N-1 번째 집까지 차례로 두 칸 떨어진 집(i-2) 혹은 세 칸 떨어진 집(i-3) 중 털었을 경우 더 많은 이득을 주는 집을 선택하여 값을 누적으로 더한다.

✏️ [2] 마지막 집을 털고 첫 번째 집을 털지 않은 경우

dp2 = [0] * N
dp2[1], dp2[2] = money[1], money[2]
for i in range(3,N):
    dp2[i] = money[i] + max(dp2[i-2],dp2[i-3])

• dp2 배열의 두 번째(1), 세 번째(2) 원소의 값을 초기화 한다.
• 네 번째(3) 집부터 마지막(N) 집까지 차례로 두 칸 떨어진 집(i-2) 혹은 세 칸 떨어진 집(i-3) 중 털었을 경우 더 많은 이득을 주는 집을 선택하여 값을 누적으로 더한다.

✍ 코드

def solution(money):
    answer = 0
    N = len(money)
    if N < 4: return max(money)

    # [1] 첫 번째 집 포함 and 마지막 집 미포함
    dp1 = [0] * N
    dp1[0], dp1[1], dp1[2] = money[0], money[1], money[0] + money[2]
    for i in range(3,N-1):
        dp1[i] = money[i] + max(dp1[i-2],dp1[i-3])
    
    # [2] 첫 번째 집 미포함 and 마지막 집 포함
    dp2 = [0] * N
    dp2[1], dp2[2] = money[1], money[2]
    for i in range(3,N):
        dp2[i] = money[i] + max(dp2[i-2],dp2[i-3])
    
    return max(max(dp1),max(dp2))