[알고리즘] 도둑질 python(프로그래머스)

 

링크: https://school.programmers.co.kr/learn/courses/30/lessons/42897#

프로그래머스

 

문제 해결 전략

이 문제는 원형으로 배치된 집들에서 도둑이 최대 금액을 털 수 있는 경우를 찾는 동적 계획법(DP) 문제입니다. 핵심은 다음과 같습니다:

1. 원형 구조 처리: 첫 번째 집을 털면 마지막 집을 털 수 없고, 반대 경우도 마찬가지입니다.
   • Case 1: 첫 번째 집을 터는 경우 (마지막 집 제외)
   • Case 2: 첫 번째 집을 털지 않는 경우 (마지막 집 포함 가능)
2. → 두 가지 경우로 분리하여 계산합니다:
3. DP 배열 설계:
   • dp[i][0]: 첫 번째 집을 턴 경우의 i번째까지 최대 금액
   • dp[i][1]: 첫 번째 집을 털지 않은 경우의 i번째까지 최대 금액
4. 각 단계에서의 최적해를 저장하기 위해 dp 배열을 사용합니다.

---

코드 설명

1. 초기화

dp = [[0, 0], [0, 0], [money[0], 0]]

• dp[0], dp[1]
• 초기 두 단계는 계산의 편의를 위해 0으로 설정합니다.
• dp[2]
  • [money[0], 0]: 첫 번째 집을 털면 2번째 집은 털 수 없습니다.
  • 0: 첫 번째 집을 털지 않으면 아직 턴 금액이 없습니다.

 

2. 메인 루프 (첫 번째 집을 턴 경우)

for ind in range(1, len(money) - 1):
    t = max(dp[-3:-1], key=lambda x: x[0])[0]
    tv = max(dp[-3:-1], key=lambda x: x[1])[1]
    dp.append([t + money[ind], tv + money[ind]])

• 슬라이싱 dp[-3:-1]→ 인접한 집을 털 수 없으므로 최소 2칸 이전의 값을 참조해야 합니다.
• 현재 집을 털기 위해 직전 2개의 DP 상태를 확인합니다.
• Case 1 (t): 첫 번째 집을 턴 경로에 현재 집 추가
• Case 2 (tv): 첫 번째 집을 털지 않은 경로에 현재 집 추가

 

 

3. 마지막 집 처리 (첫 번째 집을 털지 않은 경우)

tv = max(dp[-3:-1], key=lambda x: x[1])[1]
dp.append([tv + money[-1]])

• 첫 번째 집을 털지 않았다면 마지막 집을 털 수 있습니다.
• → 첫 번째 집을 털지 않은 경로(tv)에 마지막 집 금액을 추가합니다.

 

 

4. 최종 결과 계산

t = list(functools.reduce(lambda x,y: x + y, dp[-3:], []))
return max(t)

• 최근 3개의 DP 상태에서 모든 가능한 값을 추출하여 최대값을 선택합니다.

---

 

 

키 포인트

• 원형 구조 분리: 두 가지 경우로 나누어 선형 구조로 변환합니다.
• 슬라이싱 활용: 직전 2단계의 DP 값을 효율적으로 참조하여 인접 제약을 처리합니다.
• 공간 복잡도 최적화: 고정된 크기의 DP 배열을 유지하며 공간을 절약합니다.

 

import functools
def solution(money):
    answer = 0
    dp = [[0, 0], [0, 0], [money[0], 0]]
    
    for ind in range(1, len(money) - 1) :
        t = max(dp[-3:-1], key = lambda x: x[0])[0]
        tv = max(dp[-3:-1], key = lambda x: x[1])[1]
        dp.append([t + money[ind], tv + money[ind]])
        
    tv = max(dp[-3:-1], key = lambda x: x[1])[1]
    dp.append([tv + money[-1]])
    t = list(functools.reduce(lambda x,y: x + y, dp[-3:], []))
    return max(t)