[알고리즘] 프로그래머스 - 도둑질

프로그래머스 - 도둑질

내 풀이

def solution(money):
    dp_start = [0] * len(money) # 처음 집을 방문하는 경우
    dp_start[0] = money[0]
    dp_start[2] = dp_start[0] + money[2]

    dp_start_not = [0] * len(money) # 처음 집을 방문하지 않는 경우
    dp_start_not[1] = money[1]
    dp_start_not[2] = max(money[1], money[2])

    for i in range(3, len(money)):
        dp_start[i] = max(dp_start[i-2], dp_start[i-3]) + money[i]
        dp_start_not[i] = max(dp_start_not[i-2], dp_start_not[i-3]) + money[i]
    return max(max(dp_start[:-1]), max(dp_start_not)) # dp_start 같은 경우는 마지막집은 방문하지 못하니, 그 경우는 빼고 고려해야한다. 

프로그래머스 - 스티커 모으기(2)
와 아주 유사한 문제이다. 원형으로 되어있어, 첫 지점을 방문하는 경우와 방문하지 않는 경우로 나누고, 첫 지점을 방문하는 경우 맨 마지막은 방문한 경우를 빼야한다.