[프로그래머스-동적계획법] 도둑질_파이썬 ❌⭕

programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

---

def solution(money):
    l = len(money)

    dp0 = [0] * len(money)
    dp0[0] = money[0]
    dp0[1] = max(money[0], money[1])
    for i in range(2, l-1):
        dp0[i] = max(dp0[i-1], dp0[i-2]+money[i])

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

    return max(max(dp0), max(dp1))

아주 흔한 유형의 DP문제지만, 집이 동그랗게 배치됐다는 점이 색다르다.

집이 동그랗게 배치됐다는 뜻은 첫 번째 집과 마지막 집을 동시에 털 수 없다는 뜻이다.

따라서 첫 번째 집을 터는 경우(마지막 집을 안 터는 경우), 마지막 집을 터는 경우(첫 번째 집을 안 터는 경우)를 모두 구해서 비교해야 한다.

dp0은 첫 번째 집을 터는 경우, dp1은 마지막 집을 터는 경우이다.

---

def solution(money):
    x1, y1, z1 = money[0], money[1], money[0] + money[2]
    x2, y2, z2 = 0, money[1], money[2]
    
    for m in money[3:]:
        x1, y1, z1 = y1, z1, max(x1, y1) + m
        x2, y2, z2 = y2, z2, max(x2, y2) + m
    
    return max(x1, y1, y2, z2)

리스트를 사용하지 않는 독특한 풀이다.

x1, y1, z1은 첫 번째 집을 터는 경우고, x2, y2, z2는 마지막 집을 터는 경우이다.

z1은 마지막 집을 터는 것 까지 포함한 경우기 때문에 마지막 max 비교에서 제외시킨다.

그리고 x2보다 y2 또는 z2가 항상 크기 때문에 x2도 max 비교에서 제외시킨다.