도둑질 - 파이썬(Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42897#

프로그래머스

---

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

---

제한사항

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

---

입출력 예

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

 

---

풀이 과정

• 대놓고 dp 문제
• 주의할 점 2가지
  • 처음과 마지막도 연결되어 있으므로 처음이 털린 경우와 안털린 경우 나눠서 진행
  • 연속으로 안털수도 있으므로 max_value를 누적해서 고려해준다.

정답

def solution(money):
    answer = 0
    
    n = len(money)
    
    # 처음 터는 경우
    dp = [[0,0] for _ in range(n)]
    dp[0][1] = money[0]
    max_value = 0
    for idx in range(1, n):
        dp[idx][0] = max(dp[idx-1][1], max_value)
        dp[idx][1] = dp[idx-1][0] + money[idx]
        max_value = max(max_value, max(dp[idx]))
    
    answer = max(answer, dp[-1][0])

    # 처음 안터는 경우
    dp = [[0,0] for _ in range(n)]
    max_value = 0
    for idx in range(1, n):
        dp[idx][0] = max(dp[idx-1][1], max_value)
        dp[idx][1] = dp[idx-1][0] + money[idx]
        max_value = max(max_value, max(dp[idx]))
        
    answer = max(answer, max(dp[-1]))  
        
    return answer