[프로그래머스 Lv.4] 도둑질 (Python)

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

프로그래머스

풀이

무려 레벨 4의 문제이다. 문제만 보면 쉽게 갈피가 잡히지 않는다. 선형적으로 배치된 집들도 아니고, 원형으로 배치되어 있기에 더욱 느껴지는 난도가 높았던 것 같다.

DP 문제가 늘 그렇듯 구현 자체는 어렵지 않은데, 문제 해결을 위한 점화식을 찾는 것이 어려웠다.

 

우선 DP를 차근차근 풀어가보자. 첫 번째 집부터 도둑질을 해보겠다. 그러면 그때까지의 최댓값은 첫 번째 집의 돈과 같다.

두 번째 집까지의 최댓값은 첫 번째를 도둑질했으면 두 번째는 못하기에 최댓값은 첫째 집의 돈 또는 두 번째 집의 돈 중 최댓값이다.

다음으로 세번쨰 집에서의 최댓값은 첫 번째 집, 세 번째 집의 돈의 합 또는 두 번째 집의 돈 중 최댓값이다. 왜냐하면 붙어있는 집 둘 다 도둑질할 수는 없기 때문이다.

 

이제 위의 방식을 통해 점화식을 알아내보면 i번째 집까지의 최댓값 = max(i-2번째 집까지의 최댓값 + i번째 집의 돈, i-1번째 집까지의 최댓값)이다. 문제의 난이도에 비해 점화식만 보았을 때 난이도가 그렇게 높다고 생각할 수 없을 정도이다.

 

하지만 함정이 하나 있다. 바로 [2, 4, 13, 7, 50]과 같은 경우인데, 첫 번째 집을 도둑질했을 때 가장 돈이 많은 마지막 집은 도둑질할 수가 없게 된다. 위에서 정했던 풀이대로 생각해 보자. 그럼 세 번째 집까지의 최댓값은 max(2+13, 4) = 15이다. 네 번째 집까지 최댓값은 max(4+7, 15) = 15이다. 마지막 집에서의 최댓값은 max(15+50, 15) = 65일 것 같지만 첫 번째 집 2와 마지막 집 50은 원형 배치 시 옆집이기 때문에 둘 다 도둑질이 불가능하다.

위와 같은 문제가 있기에 반드시 둘째 집부터 시작하는 경우도 체크하도록 추가적인 구현이 필요하다. 이 부분을 알아내는 것이 어렵기에 아마 레벨 4짜리 문제가 된 게 아닐까 싶다.

def solution(money):
    arr1 = [0 for _ in range(len(money))] # 첫번째 집을 도둑질 하는 경우
    arr2 = [0 for _ in range(len(money))] # 첫번째 집을 도둑질하지 않는 경우
    
    arr1[0] = arr1[1] = money[0] # 첫번째 집은 도둑질한다고 했기에 두번째 집은 도둑질 할 수 없고, 따라서 두번째 집까지의 최댓값은 첫번째 집까지의 최댓값과 같음
    
    for i in range(2, len(money) - 1): # 세번째 집부터 마지막에서 두번째까지 DP로 계산 (마지막 집은 첫번째 집이 이미 도둑질 됐기에 도둑질이 불가능)
        arr1[i] = max(arr1[i-1], arr1[i-2] + money[i]) # i번째 집에서의 최댓값 = i-1번째 집까지의 최댓값 또는 현재 집의 돈 + i-2번째 집까지의 최댓값

    arr2[0] = 0 # 첫번째 집을 도둑질하지 않음
    arr2[1] = money[1] # 두번째 집은 도둑질됨
        
    for i in range(2, len(money)):    
        arr2[i] = max(arr2[i-1], arr2[i-2] + money[i])

    return max(max(arr1), max(arr2)) # 둘 중 더 큰 수가 정답