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]) # 둘 중 최대