[programmers] Level4. 도둑질

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

코딩테스트 연습 - 도둑질

풀이

• 동적 계획법(dynamic programming) 문제
• dp[i] : i번째 집까지 포함해 마을을 털었을 때의 최대 금액
  • dp[i] = max ( dp[i-2] + money[i] , dp[i-1])
  • 현재 집을 털때 획득 가능한 돈 + 2칸 이전 집까지 계산된 최대 금액 vs 현재 집을 털지 않고, 1칸 이전까지 계산된 최대 금액 비교
• 하지만 문제 조건에서, 원형으로 집이 배치되어있기 때문에, 첫 번째 집과 마지막 집을 동시에 털 수는 없음.
  • 첫 번째 집을 털고, 마지막 집을 털지 않았을 때의 값 -> dp[ len(money) - 1 ]
  • 첫 번째 집을 털지 않고, 마지막 집을 포함해 계산했을 떄의 값 -> dp [ len(money) ]
  • 두 개의 값 중 최댓 값을 반환
• dp[i]를 계산하기 위해, dp[i-1], dp[i-2]만 있으면 되기 때문에 변수를 2개만 두고, replace하면서 값을 계산
  • 집의 개수만큼 element를 가진 리스트를 선언할 수 있지만 여기서는 굳이 필요 없음
  • dp = [0] * len(money) 혹은 dp.append(dp[-1], dp[-2] + money)

def solution(money):
    answer = 0
    i_th = 0
    i_th_minus_1 = 0
    i_th_minus_2 = 0

    # 1. 첫 번째 집을 털었을 경우
    i_th_minus_2, i_th_minus_1 = money[0], money[0]
    # range에서 마지막 집은 포함 안함.
    for i in range(2, len(money)-1): 
        i_th = max(i_th_minus_2 + money[i], i_th_minus_1)
        i_th_minus_2, i_th_minus_1 = i_th_minus_1, i_th

       case1 = i_th

	# 2. 첫 번째 집을 털지 않고, 두 번째 집을 털었을 경우
    i_th_minus_2, i_th_minus_1 = 0, money[1]
    for i in range(2, len(money)):
        i_th = max(i_th_minus_2 + money[i], i_th_minus_1)
        i_th_minus_2, i_th_minus_1 = i_th_minus_1, i_th
    case2 = i_th

    return max(case1, case2)