[프로그래머스] 도둑질

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

코딩테스트 연습 - 도둑질

dynamic programming을 이용하여 푸는 문제입니다. 이때, dp table 두개를 tracking 해야 합니다. 

 

문제부터 간단하게 요약하면, 

도둑이 아래그림처럼 원형으로 구성된 마을을 털 계획을 하고 있는데, 인접한 두 집을 털면 경고음이 울립니다. 이 때 도둑이 털 수 있는 가장 큰 금액을 return 해야 하는 문제입니다. 

즉, solution(money)에

money: 각 집에 돈이 담긴 배열

이 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return해야 합니다. 

 

풀이를 해보도록 하겠습니다. 

 

<Solution> 

우선 5개의 집을 터는 경우를 생각해봅시다. 

다음과 같이 5번집을 터는경우, 털지 않는 경우로 나누어 생각해 볼 수 있습니다. 이렇게 되면 linear한 집들에서 털수있는 최대금액을 터는 문제로 바뀝니다. 

 

이때, 5번집을 터는 경우에는 1번집을 고려하지 않아야 하는 점이 어렵습니다.

 

5번집을 털지 않는 경우에는 1,2,3,4번 집을 터는 최댓값을 구하는 문제임으로 훨씬 수월합니다. 따라서 dp table을 두개 만들고 1번처럼 처음 값이 사라지는 경우에 대해 tracking 해주고, 2번의 경우 다른 table에서 또 tracking 해준다음 마지막으로 이 두테이블의 결과로 더 큰 값을 return 해야 합니다. 

 

실제 구현은 아래와 같습니다. 

def solution(money):
    if len(money) == 3:
        return max(money)
    # create dp
    dp1 = [0]* (len(money)+1) # track 1~n-1
    dp2 = [0]* (len(money)+1) # track 2~n-2
    
    for i in range(4, len(money)+1):
        if i == 4:
            dp1[4] = max(money[0]+money[2], money[1])
            dp2[4] = money[1]
            dp1[3] = max(money[0],money[1])
        else:
            dp1[i] = max(dp1[i-1],money[i-2]+dp1[i-2])
            dp2[i] = max(money[i-3]+dp2[i-2], dp2[i-1])

    return max(money[len(money)-1]+dp2[i], dp1[i])