[Python] 도둑질

1. 문제

 

 

 

2. 풀이 과정

방법 1) result 배열을 만들고 각 집을 털 때마다 자신보다 -2, -3인 지점으로부터 [시작점 포함한 경우, 포함하지 않은 경우] 두 값을 계산하여 저장한다.

def solution(money):
    l = len(money)
    result = [[0, 0]]
    result.append([0, money[0]]) #시작점 포함, 시작점 포함X
    result.append([money[1], 0])

    for i in range(3, l+1):
        temp = [0, 0]
        temp[0] = money[i-1] + max(result[i-2][0], result[i-3][0])
        temp[1] = money[i-1] + max(result[i-2][1], result[i-3][1])
        result.append(temp)
        
    #마지막 집은 시작점과 인접하기 때문에 result[l][1]은 생략
    #2칸 앞의 집에서는 마지막까지 오는 게 더 많은 값을 얻지만 1이 포함되어있을 땐 못오니까 확인
    return max(result[l][0], result[l-1][0], result[l-1][1], result[l-2][1])

 

 

 

방법 2) 결과 배열을 쓰지 않고, 변수 6개를 이용한다. 해당 집에서는 자신보다 -2, -3인 집의 정보만 필요하기 때문에 이 방법이 더 효율적이다.

def solution(money):
    answer = 0
    #첫 번째 집 포함 O
    x1, y1, z1 = money[0], money[1], money[0]+money[2]
    #첫 번째 집 포함 X
    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
        
    #첫 번째 집이 포함된 경우, z1(마지막 집)은 고려하지 않는다.
    #포함되지 않은 경우, x2까지 털었으면 마지막 집까지 터는 게 더 크기때문에 고려X
    return max(x1, y1, y2, z2)