[Python3]프로그래머스_도둑질

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42897#

접근법

집이 동그랗게 배치되어 있지 않다면 인덱싱을 통해
k번째 집일 경우 최대 이득은
1. k-1번째 값을 포함하는 경우
2. k-2번째 값과 k번째 집의 돈을 포함하는 경우
두 가지의 경우 중 하나를 택하면 된다.

이 문제의 경우 집이 동그랗게 배치되어 첫번째 집이 마지막 집과 연결되기 때문에 마지막 집에서의 최적의 값이 첫번째 집을 포함하는 경우라면 오답이 된다.
내가 시도한 방법은 세가지였다.

• 0번째 집 + 2번째 집 > 1번째 집일 경우 마지막집을 제외,반대의 경우 마지막집을 포함
  -> 마지막집의 돈을 전혀 고려하지 않은 케이스
  -> 반례) [1,2,3,4,100]

• 0번째 집 + 2번째 집 > 1번째 집 + 마지막 집일 경우 마지막집을 제외,반대의 경우 마지막집을 포함
  -> 위 두 알고리즘들은 0번째와 2번째 집이 근처의 집들보다 클 경우 무조건적으로 포함한다.
  -> 반례) [1,3,9,11,1,1,2] 의 경우 0번째와 2번째 집을 포함하는 경우 3번째 집은 포함되지 않게 된다.

• 마지막 집이 포함/포함되지 않아야 하는 지 바로 알 수는 없었다.
  그래서 0번째 집을 포함/미포함 시키는 경우로 나누어 모든 경우를 고려하였다.
  -> 0번째 집을 포함 = 1번째 집에서의 최적은 0번째 집을 포함하고 1번째 집은 미포함
  -> 0번째 집을 미포함 = 2번째에서의 최적은 1번째 집만 포함하거나 2번째 집만 포함하는 경우

코드

def solution(money):
    answer = 0
    m = money[:]
    m[1] = m[0]
    for i in range(2,len(m)):
        if( m[i-2]+m[i] > m[i-1]  ):
            m[i] = m[i-2]+m[i]
        else:
            m[i] = m[i-1]
    money[2] = max(money[1],money[2])
    for i in range(3,len(money)):
        if( money[i-2]+money[i] > money[i-1]  ):
            money[i] = money[i-2]+money[i]
        else:
            money[i] = money[i-1]
    return max(money[-1],m[-2])