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

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

코딩테스트 연습 - 도둑질

이 문제는 첫번째 집부터 마지막 집까지 하나씩 추가하면서 최대가 될 수 있도록 값을 구하면 된다. 인접한 두 집은 털 수 없기 때문에 "현재 i번째 집 money + i-2번째 집 money" 와 "i-1번째 집 money" 중 더 큰 값을 선택하면 된다. 

즉, 점화식은 dp[i] = max(dp[i-2] + money[i], dp[i-1]) 가 된다.

 

이 문제는 원형으로 연결되었기 때문에 첫번째 집과 마지막 집이 연결되어 있어서 모두 털 수는 없다. 따라서 두 가지로 나눠서 생각해야 한다.

 

1. 첫번째 집을 털고 마지막 집을 털지 않는 경우

2. 첫번째 집을 털지 않고 마지막 집에게 선택권을 주는 경우

 

def solution(money):
    f_dp = [money[0], money[0] + 0] # 첫번째 집을 터는 경우 - 첫번째 집 털고 두번째 집은 못 턴다
    l_dp = [0, 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]) # 두 경우 중 최대값을 리턴

두 가지 경우의 수 중 최대값을 리턴해야 하기 때문에 두 개의 리스트를 생성한다. for 문을 통해 집을 돌면서 최대값을 구한다.  첫번째 집을 털 때는 마지막 집은 못 터니까 len(money) -1 까지만 반복문을 돈다. 두 경우의 수를 다 구했으면 두 경우 중 최대값을 리턴하면 된다.