[dp] 도둑질

프로그래머스

 

연속된 두 집을 선택하지 않으면서 합의 최대를 구하는 것이 관건인 문제다.

 

현재 훔쳐야할 집이 i번째 집이라면 i번째 집을 훔칠지 말지 경우를 나눠 dp를 구할 수 있다. i번째집을 훔칠 수 있는 경우는 i - 1번째 집을 훔치지 않았을 경우이며 이를 식으로 나타내면,

 

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

 

로 나타낼 수 있다

 

이때 dp는 선형일 경우로 진행하기 때문에 원형인 구조인 지금 상황에서는 첫번째 집을 훔쳤는지 안 훔쳤는지에 따라서 두 번 경우를 나눠 최대값을 구해줘야 한다. 이유는 dp라는 알고리즘 특성상 2번째 배열부터 for문을 돌려야 하는데, 초기값이 두 가지로 나뉘므로 dp의 모든 결과도 다를 수밖에 없다. 

 

1) 0번째 집을 선택하지 않았을 경우

마지막 집을 선택할 수 있으며, 이 경우 dp[0] = 0, dp[1] = money[1]

 

2) 0번째 집을 선택했을 경우

마지막 집을 선택할 수 없으며, 이 경우 dp[0] = money[0], dp[1] = money[0](첫번째 집을 선택했으므로 1번째 집은 선택할 수 없다)

 

def solution(money):
    answer = 0
    
    size = len(money)
    dp = [0] * size
    
    dp[0] = 0
    dp[1] = money[1]
    
    # 첫번째 집이 선택이 안 됐을 경우
    for i in range(2, size) :
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
    
    answer = dp[size - 1]
    
    dp[0] = money[0]
    dp[1] = money[0]
    
    # 첫번째 집이 선택이 됐을 경우
    for i in range(2, size - 1) :
        dp[i] = max(dp[i - 1], dp[i - 2] + money[i])
    
    answer = max(answer, dp[size - 2])
    
    return answer