프로그래머스: 도둑질

문제

코딩테스트 연습 - 도둑질

 

문제 풀이

 인접한 두 집은 방범장치가 연결되어 털 수 없다는 제한 조건을 가지고 있다. 이때 집을 털어서 가장 큰돈을 훔칠 수 있는 최댓값을 반환하는 문제이다. 문제를 풀기 위해서는 다음과 같은 경우를 생각하면 쉽게 해결할 수 있다.

 

• 집 1개 : 해당 집을 터는 것이 최대 값이다.
• 집 2개 : 둘 중에 `money`가 큰 것을 터는 것이 최대 값이다.
• 집 3개 : `i와 i - 2` 또는 `i - 1` 집의 `money` 중 최대값인 경우를 터는 것이 최대이다.
• 집 3개 인 경우에서 알 수 있듯이 경우의 수가 다시 2가지로 나뉜다.
  • 첫 번째 집을 무조건 터는 경우.
    • `dp[FIRST][0], dp[FIRST][1] = money[0], moeny[0]`로 초기화 한다.
  • 마지막 집을 무조건 터는 경우.
    
    • `dp[LAST][0], dp[LAST][1] = 0, money[1]`로 초기화 한다.

 위와 같은 경우를 통해 집을 털 수 있는 최대값은 점화식은 `dp[i] = max(dp[i - 1], money[i], dp[i - 2])`을 유추할 수 있다.

 

코드

FIRST, LAST = 0, 1


def solution(money):
    length = len(money)
    dp = [[0] * length for _ in range(2)]
    dp[FIRST][0], dp[FIRST][1] = money[0], money[0]
    dp[LAST][0], dp[LAST][1] = 0, money[1]

    for i in range(2, length):
        if i < length - 1:
            dp[FIRST][i] = max(dp[FIRST][i - 1], money[i] + dp[FIRST][i - 2])
        dp[LAST][i] = max(dp[LAST][i - 1], money[i] + dp[LAST][i - 2])

    return max(max(dp[FIRST]), max(dp[LAST]))