[프로그래머스][Python] 도둑질

문제를 정리해보자.

아래 그림과 같이 집이 동그랗게 배치된 마을이 있다.
도둑은 이 마을을 털 계획이다. 하지만 인접한 두 집을 털면 경보가 울리게 되어 있다.
그래서 도둑은 경보가 울리지 않게 마을을 털 것이다.
각 집에 돈이 담겨 있을 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구하자.

 

풀이를 생각해보자.

이 문제에서 주의해야 할 점은 2가지이다.

1. 인접한 두 집을 털면 안 된다.
2. 집이 원형 모양으로 배치되어 있다.

 

[91, 90, 5, 7, 5, 7]

위 그림과 같은 마을이 있다고 하자.

첫 번째 집을 방문하면, 두 번째 집과 여섯 번째 집은 방문하지 못한다.
두 번째 집을 방문하면, 첫 번째 집과 세 번째 집은 방문하지 못한다.
다른 집도 마찬가지이다.

집을 1차원상에 두고 생각해보자.

 

 

 

 

그리고 조건 1을 보자.

두 집이 인접하지 않고, 최대한 많은 돈을 털어야 한다.

 

 

 

 

위 그림처럼 앞앞앞 집, 앞앞 집을 방문하고, (앞 집은 인접한 집이기 때문이다.)

방문한 집의 돈을 자신의 집의 돈과 더해서 누적시킨다.

 

그리고 누적된 2개의 값 중 더 큰 값만 남긴다.

 

코드로 작성하면 이렇다.

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

 

이제 조건 2를 보자.

 

집은 원형 모양으로 배치되어 있기 때문에, 첫 번째 집과 마지막 집이 인접한다.

따라서 첫 번째 집을 방문했을 때와, 방문하지 않았을 때의 경우를 나눠야 한다.

 

 

 

그리고 첫 번째 집을 방문하면 마지막 집을 방문하지 못한다.

 

구현해보자.

 

def solution(money):
    l = len(money)

    f_dp = [0] * l  # 첫 번째 집 포함
    s_dp = [0] * l  # 첫 번째 집 미포함

    # 첫 번째 집
    f_dp[0] = money[0]
    s_dp[0] = 0

    # 두 번째 집
    f_dp[1] = 0
    s_dp[1] = money[1]

    # 세 번째 집
    f_dp[2] = money[0] + money[2]
    s_dp[2] = money[2]

    for i in range(3, l):
        f_dp[i] = max(f_dp[i-3], f_dp[i-2]) + money[i]
        s_dp[i] = max(s_dp[i-3], s_dp[i-2]) + money[i]
    
    # 마지막 집, 방문x
    f_dp[l-1] -= money[l-1]

    return max(max(f_dp), max(s_dp))

 

시간복잡도는 O(N)이다.