[DP] 집에서 값나가는 물건 훔치기

DP 연습문제 : 집에서 값나가는 물건 훔치기

흥미로운 문제입니다. DP 를 연습하시는 분에게 꼭 추천드리는 문제입니다.

문제

총 $n$ 개의 집들이 한 거리에 일렬로 있습니다. 집 안에는 각자 중요한 물건들이 있습니다. 한 도둑이 각 집에서 가장 중요한 물건들을 훔쳐서 최대의 이득을 얻으려합니다. 하지만 도둑은 전략적으로 움직이죠. 도둑은 절대로 훔친 집에서 인근한 집의 물건은 훔치지 않습니다. 왜냐면 물건이 사라진 집은 그 집의 집주인이 자기 집을 기준으로 왼쪽집과 오른쪽 집에 경고를 하기 때문에 경찰에 걸릴 수 있거든요. 도둑을 도와(?)서 물건들을 훔쳤을때 최대의 값어치가 나가게끔 해주세요.

예제:

입력값  : hval[] = {6, 7, 1, 3, 8, 2, 4}
출력값  : 19
도둑은 6, 1, 8, 4 의 값이 나가는 물건을 훔칠겁니다.

입력값  : hval[] = {5, 3, 4, 11, 2}
출력값 : 16
도둑은 5, 11 의 값이 나가는 물건을 훔칠겁니다.

문제를 먼저 풀어보세요. 비슷한 문제가 2개 있습니다. 풀이 방법은 둘다 같습니다.
1번, 2번

정답

대부분의 재귀문제는 재귀로 시작해서 tabulation 이나 memoization 을 붙이는걸로 끝납니다. 이 문제도 마찬가지 입니다.

도둑이 $i$ 번째 집에 들릴때 두가지 선택이 있습니다. 물건을 훔치거나 내버려두거나죠. $dp[i]$ 를 $i$ 번째 집까지 들렸을때 훔칠수 있는 물건 값의 최대치라고 하겠습니다. 그렇다면 $dp[i]$ 는 다음과 같이 계산됩니다.

dp[i] = max (hval[i] + dp[i-2], dp[i-1])

여기서 hval[i] + dp[i-2] 는 $i$ 번째 집에 물건을 도둑이 훔치기로 결정했을 때 입니다. 이 선택에서 훔칠 수 있는 물건 값의 최대치는

'현재 $i$ 번째 집에 있는 물건 값 + $i-2$ 번째 집 까지 들렸을때 훔칠 수 있는 물건 값의 최대치'

가 됩니다. $i-1$ 이 아니라 왜 $i-2$ 나면, $i-1$ 번째 집은 $i$ 번째와 이웃해 있기 때문에 $i-1$ 번째의 집 물건까지 훔쳤다가는 경찰에 잡힐 수 있다고 문제에 명시되어 있기 때문입니다.

dp[i-1] 는 $i$ 번째 집의 물건을 훔치지 않기로 결정했을 때 입니다. 이때는 현재 도둑이 훔치고 있는 값들에 $i$ 번째 물건의 값어치가 추가되지 않으므로 dp[i] = dp[i-1] 를 해주고 넘어갑니다.

이렇게되면 도둑은 '훔칠까? 훔치지 말까?' 의 두가지 옵션을 동시에 고려하면서 $i$ 번째 집에 도달할때까지 물건 값의 최대치를 계산하게 될것입니다.

이제 이 수식을 위의 $dp$ 배열을 통해 bottom up 방식으로 계산해보겠습니다. 코드는 아래와 같습니다.

# 훔친 값의 최대치를 계산하는 python 3 프로그램
 
# 훔친 값의 최대치를 계산한다. 
def maximize_loot(hval, n):
    if n == 0:
        return 0
    if n == 1:
        return hval[0]
    if n == 2:
        return max(hval[0], hval[1])
 
    # dp[i] 는 i 번째 집까지 도달한뒤에 
    # 그때까지 훔친 값의 최대치를 의미한다. 
    dp = [0]*n
 
    # dp[0] 와 d[1] 를 초기화 한다. 
    dp[0] = hval[0]
    dp[1] = max(hval[0], hval[1])
     
    # 나머지 dp 배열을 채운다.
    for i in range(2, n):
        dp[i] = max(hval[i]+dp[i-2], dp[i-1])
 
    return dp[-1]
 
# 테스트를 위한 드라이버 프로그램
def main():
 
    # 집에 있는 물건의 값어치들
    hval = [6, 7, 1, 3, 8, 2, 4]
 
    # 총 집의 개수
    n = len(hval)
    print("Maximum loot value : {}".
        format(maximize_loot(hval, n)))
 
if __name__ == '__main__':
    main()

출력값

Maximum loot value : 19

위 알고리즘의 시간 복잡도와 공간 복잡도는 모두 $O(n)$ 입니다. 시간 복잡도는 더이상 줄일 수 없지만, 공간 복잡도를 간단하게 $O(1)$ 로 만들 수 있습니다.
자세히 코드를 들여다 보시면, 우리는 원하는 값을 찾기 위해 계속해서 2가지 변수만 이용하고 있음을 알 수 있습니다. dp[i-1] 하고 dp[i-2] 입니다. 그래서 이 두가지를 일반 변수로 사용해서 정답을 찾겠습니다.

# 훔친 값의 최대치를 계산하는 python 3 프로그램
 
# 훔친 값의 최대치를 계산한다. 
def maximize_loot(hval, n):
    if n == 0:
        return 0
 
    value1 = hval[0]
    if n == 1:
        return value1
 
    value2 = max(hval[0], hval[1])
    if n == 2:
        return value2
 
    # 마지막에 훔친 값의 최대치를 저장하는 변수
    max_val = None
 
    # 값을 채운다.
    for i in range(2, n):
        max_val = max(hval[i]+value1, value2)
        value1 = value2
        value2 = max_val
 
    return max_val
 
# 테스트를 위한 드라이버 프로그램
def main():
 
    # 집에 있는 물건의 값어치들
    hval = [6, 7, 1, 3, 8, 2, 4]
 
    # 총 집의 개수
    n = len(hval)
    print("Maximum loot value : {}".format(maximize_loot(hval, n)))
 
if __name__ == '__main__':
    main()

출력값

Maximum loot value : 19

처음 코드와 다른점은 dp[i] 를 max_val 로 바꿨다는 점이고, 또한 dp[i-2]=value1, dp[i-1]=value2 로 수정했다는 점입니다. 그런데 바로 dp[i] = max_val 이 되는것은 아니고 bottom up 방식으로 쌓아나가는 점은 변하지 않았으므로 (그래서 시간복잡도는 똑같이 $O(n)$), i < n 일때 계산된 value1 는 value2 로, 그리고 value2 은 max_val 로 바뀌게 됩니다.

왜 이렇게 바뀔까요? 여기서 다시 상기하셔야할 점은 value1 은 dp[i-2] 로 $i-2$ 번째 집까지 도둑질을 했을때의 최대값을 말한다는 것입니다. 그리고 value2 는 dp[i-1] 로 $i-1$ 번 집까지 도둑질을 했을때의 최대값을 말하죠. max_val 변수는 max_val = max(hval[i]+value1, value2) 와 같이 위에서 배운대로 계산되고, 계산된 순간에서는max_val = dp[i] 이지만 i 가 loop 를 통해 그 다음으로 넘어가게 된다면 max_ val 은 dp[i-1] 이 되는것이고 value1 = dp[i-3] ,value2 =dp[i-2] 가 되는것이죠. 즉, value1, value2 를 각각 다시 dp[i-2],dp[i-1]로 만들어 주기 위해서는 value1 = max_val, value1 = value2 가 되야 합니다.

---

이 문제는 동전 교환 문제와 비슷한거 같습니다.

이 기사는 Atul Kumar가 작성한 글을 참조해 재구성 하였습니다.