도둑질

Posted on In , ,

문제정의

인접한 집을 털지 않으면서 최대한 많은 돈을 도둑질하는 문제이다. 이 때 집은 원형으로 이어져 있다고 가정하기 때문에 첫번째 인덱스와 마지막 인덱스가 이어져있다. 문제 링크

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(money):
    dp1 = [0] * (len(money)-1)
    dp1[0] = money[0]
    dp1[1] = max(money[0], money[1])
    for i in range(2, len(money)-1):
        dp1[i] = max(dp1[i-1], money[i]+dp1[i-2])

    dp2 = [0] * len(money)
    dp2[0] = 0
    dp2[1] = money[1]
    for i in range(2, len(money)):
        dp2[i] = max(dp2[i-1], money[i]+dp2[i-2])
    
    return max(dp1[-1], dp2[-1])

집이 원형으로 이어져있을 때의 조건을 생각하지 못해서 결국 풀이를 봤다. 결론적으로 말하면 첫번째집과 마지막집은 동시에 선택하지 못한다! 그래서 이 경우를 둘로 나눠서 생각한다.

  1. 마지막 집을 제외하고 도둑질 할 수 있는 최대 금액을 찾는다.
  2. 첫번째 집을 제외하고 도둑질 할 수 있는 최대 금액을 찾는다.
  3. 위의 두 값 중에서 큰 값을 반환한다.

이렇게 하면 겹치는 케이스가 존재할 수 있지만 적어도 피하려고 하는 케이스만을 제외하고 나머지 경우의 수를 다 구할 수 있다.

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

테스트


테스트 화면


DP는 너무 어렵다.. 유형중에 제일 해보지 않아서 어색하다. 백준에서 DP문제만 골라 풀어봐야겠다.