[프로그래머스] 도둑질, 파이썬

🔗 문제 ∙ 도둑질

문제

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

제한 사항

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

입출력 예

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

🔑 풀이

2579번: 계단 오르기와 2156번 : 포도주 시식 1149번: RGB 거리 풀이 방법과 유사하다.
각 단계가 인접한 i-1, i+1 단계에서 오지 못하거나 가지 못하는 경우의 문제들이다.

이 문제의 경우 아래와 같은 점을 고려해야 한다.

• i-1, i+1 의 인접한 두 집을 털 경우 경보가 울린다.
• 마을이 동그랗게 이어져 있기 때문에, 첫번째와 마지막 집 또한 이웃이다.

첫번째 집과 마지막 집 또한 이웃이라는 점을 어떻게 고려해서 구현해야할지 몰랐기 때문에, 처음에는 그 점을 고려하지 않고 문제를 풀어보았다. 즉 마을이 원형이 아닌 일자 형태로 있다고 생각하였다.

첫 집 부터, 마지막 집까지 하나씩 추가하면서 최대로 가져올 수 있는 값을 구한다.
집이 하나 있을 경우, 그 집을 터는게 최대값
집이 두 개 있을 경우, 인접한 집을 털지 못하므로 두 집 중 money가 큰 집을 턴다.
집이 3 개만 있을 때, 현재 i 집 money + i-2 번째 집 money 혹은 i-1집 money 중 더 큰 값을 가져오면 된다.

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

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

하지만, 첫 집과 마지막 집이 둘다 포함되는 경우가 생길 수 있기 때문에
1) 첫 번째 집을 무조건 털고, 마지막 집은 털지 않는 경우
2) 마지막 집을 무조건 털고 첫 번째 집은 털지 않는 경우
로 나눠서 생각해야 한다.

코드

def solution(money):
    dp1 = [0] * len(money)
    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(max(dp1), max(dp2)) # 두 경우 중 최대