도둑질

문제 설명

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

풀이

집이 하나 있을 경우 그 집을 터는게 최대 값. 집이 두 개 있을 경우, 인접한 집을 털지 못하도록 두 집중 money가 큰 집을 턴다. 집이 3개만 있을 떄, 현재 i집 money + i-2번째 집까지의 최대값 혹은 i-1집까지의 최댓값중 더 큰 값을 가져오면 된다.

아래와 같은 점화식이 나온다.

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

하지만 원형이기 때문에, 첫 집과 마지막 집이 둘다 포함되는 경우가 생길 수 있습니다. 따라서 다음 2가지를 생각해야 합니다

1) 첫번째 집을 무조건 털고 마지막 집은 털지 않는 경우

2) 첫번째 집을 털지 않고, 마지막 집은 터는 경우

이를 위해 최댓값을 담아두는 d 리스트에 차원을 하나 추가하여 첫번째 원소를 포함했는지 안했는지를 기록합니다. 최종적으로 d[-1][1]에서는 첫번째 집을 포함하지 않고 마지막 집을 포함한 최댓값이 담깁니다. 또한 d[-2][0]에서는 첫번째 집을 포함하고 마지막 집을 포함하지 않은 최댓값이 담길것입니다. 최종적으로 이 두개중 최댓값을 리턴하면 됩니다.

def solution(money):
    d = [[0,0],[0,0],[money[0],0]]
    for i in range(3, len(money)+3):
        if i-2 == len(money):
            break
        a = max(d[i-2][0] + money[i-2], d[i-1][0])
        b = max(d[i-2][1] + money[i-2], d[i-1][1])
        d.append([a,b])

    return max(d[-2][0], d[-1][1])