[프로그래머스] 도둑질

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

프로그래머스

 

해결 아이디어를 떠올리기 어려웠던 DP 문제이다.

다른 사람의 풀이를 참고 했는데 경우의 수를 나눠서 복잡한 문제를 단순히 만드는게 풀이의 핵심이었다.

 

N개의 집이 있는 한 마을을 도둑이 털 계획을 하고 있다.

단, 각 집은 원형으로 이어져 있으며 집을 털때 서로 인접해 있는 두 개의 집을 털 수 없다. 

각 집마다 털 수 있는 돈이 배열로 주어졌을때 도둑이 이 마을에서 털 수 있는 금액의 최대값을 찾는 문제이다.

 

내가 생각한 풀이 방법

나는 DP 문제를 풀때 먼저 완전 탐색으로 문제를 해결할 수 있는지 확인하고

그 안에서 중복이 발견되면 그것을 없애는 방법으로 최적화해 나간다.

 

그래서 빈 마을에 1번 집부터 순서대로 추가하면서 도둑이 어떤 조합으로 집을 털었을때 최대인지 계산하기 위해서

마을에 집이 i 만큼 있을때 조건을 만족하면서 도둑이 털 수 있는 집들의 모든 조합을 배열의 i 번째 인덱스에 저장했다.

그래서 새로운 i+1 번째 집이 추가된 마을에서 조합을 계산할때 i 번째 인덱스에 저장된 값을 활용하려고 했다.

 

그러나 이런 방식은 중복을 제외하더라도 조합의 가짓 수를 배열에 저장해야하기 때문에

O(N^2) 만큼의 메모리와 시간을 사용해서 허용치를 초과하게 되어 다른 방법을 참고했다.

 

풀이

집이 원형이 아니라 선형으로 돼있다고 가정해보자.

도둑은 최대한으로 돈을 털기 위해 처음 집부터 마지막 집까지 순서대로 각 집을 털지 말지 고려할 것이다.

i를 0부터 N까지 반복하면서 i 번째 집까지 고려했을때 털 수 있는 돈의 최대값을 배열의 i 번째 인덱스에 저장한다.

이 상태에서 i+1번째 집을 털 경우와 아닌 경우로 나누어 생각해볼 수 있다.

(1) i+1번째 집을 털었을때 : (i-1 번째 집까지 고려한 최댓값) + (i+1 번째 집에서 털 수 있는 돈)

(2) i+1번째 집을 털지 않았을때 : i 번째 집까지 고려한 최댓값

두 경우 중 최댓값이 i+1번째 집까지 고려한 최댓값이 된다.

 

마을이 원형일때는 처음 집과 마지막 집을 동시에 털 수 없으므로

(1) 첫 번째 집을 털지 않고 마지막 집까지 고려한 경우

(2) 첫 번째 집부터 고려하되 마지막 집을 털지 않는 경우

두 경우 중 돈을 최대로 털 수 있는 경우가 정답이 된다.

 

def solution(money):
    answer = 0
    n = len(money)
    d1 = [money[0], max(money[0], money[1])] + [0]*(n-2)
    d2 = [0, money[1]] + [0]*(n-2)
    for i in range(2, n):
        if i < n-1:
            d1[i] = max(d1[i-2] + money[i], d1[i-1])
        d2[i] = max(d2[i-2] + money[i], d2[i-1])
    return max(max(d1), max(d2))