프로그래머스_python_도둑질

문제

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

코딩테스트 연습 - 도둑질

풀이

dp에 해당 위치에서 얻을 수 있는 최대값을 저장한다.

dp[i] = max(i-1번째 집을 털때 최대값, i-2번째 집과 i번째 집을 털때의 최대값)

 

1. -1번째, 1번째 집을 건너뛴다.

2. 0번째 집을 건너 뛴다.

초기 경우를 둘로 나누어서 최댓값을 구한다.

코드

def solution(money):    
    answer = list()
    
    # -1번째, 1번째 집을 건너뛴다.
    dp = [m for m in money]
    dp[-1] = 0
    dp[1] = max(dp[0], dp[1])
    
    for i in range(2, len(money)) : 
        dp[i] = max(dp[i-1], dp[i-2]+dp[i])
    answer.append(dp[-1])

    # 0번째 집을 건너뛴다.
    dp = [m for m in money]
    dp[0] = 0
    
    for i in range(2, len(money)) : 
        dp[i] = max(dp[i-1], dp[i-2]+dp[i])
    answer.append(dp[-1])
        
    return max(answer)