(파이썬) [알고리즘 문제 풀이] - 도둑질 (프로그래머스)

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

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

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

제한사항

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

 

풀이

저는 이 문제를 다이나믹 프로그래밍으로 풀었습니다.

이 문제에서 가장 중요한 포인트는 인접한 두 집을 털수 없다는 것입니다.

예를 들어 다음과 같은 테이블이 있다고 하면,

money = [2,5,6]

다이나믹 프로그래밍을 위해 초기값을 0하며 money 리스트와 같은 사이즈의 리스트를 만듭니다.

dp = [0,0,0]

첫번째 집만 털수 있는 경우 무조건 첫번째 집을 털어야 최대값이기 때문에

dp = [2,0,0] 

그 다음 두번째 집까지 털수 있는 경우

우리는 첫번째 집과 두번째 집 중에 더 높은 값을 선택할수 있습니다. 그래서,

dp = [2,5,0]

자 이제 중요한 세번째 집까지 털수 있는 경우를 보겠습니다.

여기서 우리는 두가지 선택을 할수 있습니다.

• 첫번째 집과 세번째 집을 턴다. -> money[0] + money[2] = 2 + 6 = 8
• 두번째 집을 턴다. -> money[1] = 5

8은 5보다 크기 때문에 우리는 첫번째 집과 세번째 집을 터는 경우를 선택합니다.

dp = [2,5,8]

이런 방식으로 더 큰 크기의 리스트도 최대값을 계산 가능합니다.

임의의 수 i에 대하여 다음과 같은 식이 완성 됩니다.

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

여기서 끝난것 같지만 문제가 있습니다.

이 마을은 동그랗게 배치되어 있기 때문에 첫번째 집과 마지막 집은 둘다 털수가 없습니다.

그래서 두가지 경우를 준비합니다.

예를 들어, money = [4,7,2,5,8] 라는 리스트가 있습니다.

• 첫번째 집이 포함되고 마지막 집이 포함 안된 경우 dp = [4,7,2,5]

• 첫번째 집이 포함되지 않고 마지막 집이 포함 된 경우 dp = [7,2,5,8]

이렇게 두가지 경우로 각각 최대값을 구한 다음에

둘 중에 더 높은 값을 택하면 됩니다.

코드

def solution(money):
    dp1,dp2 = [], []
    for h in money[1:]:
        dp1.append(0)
        dp2.append(0)
        
    dp1[0],dp2[0] = money[0], money[1]    
    dp1[1], dp2[1] = max(dp1[0], money[1]), max(dp2[0], money[2])
    
    for i in range(2,len(money)-1):
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i])        
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i+1])  
    
    return max(dp1[-1], dp2[-1])