[프로그래머스 / Python] 도둑질

문제 링크: programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

 

 

문제 설명

도둑이 훔칠 수 있는 돈의 최댓값을 저장하는 dp 테이블을 생성합니다. dp[i]는 1번부터 i번째 집까지 털었을 때 훔칠 수 있는 돈의 최댓값입니다.

 

만약 이전 집을 털었다면 현재 집은 털지 못하므로 dp[i]는 (바로 전 집까지 훔칠 수 있는 최댓값)와 (전전집까지의 훔칠 수 있는 최댓값 + 현재 집의 money) 두 가지 경우로 나뉩니다. 

 

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

 

이때 마지막 집은 첫 번째 집과 방범장치가 연결되어 있으므로 dp테이블 계산을 1번 집을 털 경우/ 안 털 경우로 나눠서 수행했습니다. 

 

1번 집을 털 경우: 2번부터 마지막 바로 전 집까지 훔칠 수 있는 돈 계산(마지막 집은 털지 못함)

1번 집을 털지 않을 경우: 2번부터 마지막 집까지 훔칠 수 있는 돈 계산

 

이후에 두 가지 경우 중 더 큰 값을 반환합니다. 

 

 

 

 

소스코드

def solution(money):
    dp1 = [0] * len(money)
    dp2 = [0] * len(money)
    # 1번 집을 터는 경우
    dp1[0] = money[0]
    for i in range(1, len(money) - 1):  # 마지막 집은 털지 못함
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])
    # 1번 집을 안터는 경우
    dp1[0] = 0
    for i in range(1, len(money)):
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])

    return max(dp1[-2], dp2[-1])