도둑질 (python)

프로그래머스 문제 - 도둑질 LV3

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

👀 깃헙 소스

문제설명

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

입출력 예

money	      return
[1, 2, 3, 1]	4

솔루션

크게 두가지 경우로 나눠서 메모제이션 기법을 사용하면 된다
i) 첫 번째 집 털었을 때
ii) 첫 번째 집 못 털었을 때

코드

def solution(money):
    # 첫 번째 집 털었을 때 = [첫 집 털 때, 첫 집 털고 둘째 집 못 털 때]
    f_dp = [money[0], money[0] + 0]
    # 첫 번째 집 못 털었을 때 = [0, 첫 집 못 털고 둘째 집 털 때]
    l_dp = [0, money[1]]
    
    # 마지막집은 못터니까 len(money)-1까지
    for i in range(2, len(money)-1):
        # 전 집 못 털었을때 + 지금집 털때 ,지금집 못털 때(바로 전까지 메모제이션해둔 값과 동일) 값 중 최대
        f_dp.append(max(f_dp[i-2] + money[i], f_dp[i-1]))
        
    for i in range(2, len(money)):
        l_dp.append(max(l_dp[i-2] + money[i], l_dp[i-1]))

    return max(f_dp[-1], l_dp[-1]) # 둘 중 최대