[도둑질/LV4/Python3]

프로그래머스 도둑질 LV4

 

문제
도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

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

money	return
[1,2,3,1]	4

 

 

 

문제에서 조심해야 하는 경우는 2가지이다.

1. 이전 집을 도둑질 하고 다음 집도 도둑질을 하는 경우

2. 처음 집을 도둑질을 하고 마지막 집도 도둑질을 하는 경우  도시가 원형임에 주의

 

 

이전 집을 털었는지의 여부를 구분해야 하기 때문에 2차원 배열을 사용한다.

i번째 집을 털었을 때의 최댓값은 i-1번째 집을 털지 않은 경우 중 최댓값 + i번째 집의 돈

i번째 집을 털지 않았을 때의 최댓값은 i번째 집을 턴 경우와 i번째 집을 털지 않은 경우 중 최댓값이다.

 

위 조건에 맞게 점화식을 나타낸다면 다음과 같다.  0은 털지 않은 경우, 1은 턴 경우이다.

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

 

 

첫번째 집을 털었다면, 마지막 집은 털지 못한다. 반대로, 첫번째 집을 안털었다면, 마지막 집을 털 수 있다.

첫번째 집을 턴 경우 중 최댓값과, 첫번째 집을 털지 않은 경우 중 최댓값을 2개로 나누어 구했다

 

def solution(money):
    dp = [[0] * len(money) for _ in range(2)]
    dp[1][0] = money[0]
    
    for i in range(1, len(money)):
        dp[1][i] = max(dp[0][i-1], dp[1][i-2]) + money[i]
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
    answer = dp[0][-1]
    
    dp = [[0] * len(money) for _ in range(2)]
    for i in range(1, len(money)):
        dp[1][i] = max(dp[0][i-1], dp[1][i-2]) + money[i]
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
    answer = max(answer, dp[1][-1])
    
    return answer

 

위 코드는 O(N)의 시간 복잡도를 가지게된다.

 

---