[프로그래머스] 도둑질

문제

• 한 마을의 집이 동그랗게 배치되어 있고, 인접한 집들은 방범장치가 연결되어 있어 도둑이 하나의 집을 털면 인접한 두 집에도 경보가 울린다.
• 각 집에서 얻을 수 있는 돈이 주어질 때 도둑이 훔칠 수 있는 돈의 최댓값 구하기
• 3 <= 마을의 집 개수 <= 1,000,000

 

풀이

• dp[n] : n번째 집까지 털었을 때 최댓값
  • dp[i] = (i번째 집을 털지 않음, i번째 집을 터는 경우)
  • i 번째 집을 털지 않음 = dp[i-1]
  • i 번째 집을 터는 경우 = dp[i-2] + money[i]
• 첫 번째 집을 터는 경우와 털지 않는 경우 이렇게 2개로 나눌 수 있다.

 

def solution(money):
    n = len(money)
    
    # dp[n] : n번째 집까지 털었을 때 최댓값
    dp = [0] * n
    # 첫번째 집을 터는 경우
    dp[0], dp[1] = money[0], max(money[0], money[1])
    for i in range(2, n-1) :
        # i번째 집 털지 않음 vs i번째 집 터는 경우 비교
        dp[i] = max(dp[i-1], money[i] + dp[i-2])
    answer = max(dp)

    # 첫번째 집을 털지 않는 경우
    dp = [0] * n
    dp[1] = money[1]
    for i in range(2, n) :
        # i번째 집 털지 않음 vs i번째 집 터는 경우 비교
        dp[i] = max(dp[i-1], money[i] + dp[i-2])
    answer = max(answer, max(dp))
    
    return answer

 

References

• 프로그래머스 고득점Kit DP