프로그래머스 - 도둑질 (Dynamic Programming) / Level 4

출처 : https://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

 

 

풀이

def solution(money):
    
    dp = [0 for i in range(len(money))]
    
    # 첫 번째 집을 털 경우
    dp[0] = money[0]
    dp[1] = dp[0]
    
    for i in range(2, len(money) - 1):
        dp[i] = max(dp[i-1], dp[i-2] + money[i])
        
    value = max(dp)
    
    # 첫 번째 집을 털지 않을 경우
    dp = [0 for i in range(len(money))]
    dp[1] = money[1]
    
    for i in range(2, len(money)):
        dp[i] = max(dp[i-1], dp[i-2] + money[i])
    
    return max(value, max(dp))

풀이에 실패하여 다른 사람들의 코드를 분석해봤다.

DP를 풀 때는 dp배열을 어떤 의미로서 정의할 것인지

그리고 dp[i] 일반항을 어떻게 다른 항들로 표현할 수 있는지 (즉, 점화식을 도출해낼 수 있는지)

마지막으로 앞선 원칙에 따라 dp배열을 채워 나가는 것이 중요하다.

 

이 문제에서 dp[i]는 i개의 집을 털었을 때의 최댓값으로 정의했다.

그러므로 매 순간 i-1번째 집만 터는 경우와 i-2번째 집과 i번째 집을 터는 것 중 최댓값을 선택하면 된다.

추가적으로 집들이 일렬로 있는 것이 아닌 원형으로 있기 때문에 첫 번째 집과 마지막 집 각각  한 번씩 선택하는 

경우로 나누어 풀어주어야 한다.