[프로그래머스] 도둑질

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

코딩테스트 연습 - 도둑질

 

프로그래머스 4단계 문제치고는 쉬운 문제였다. 원형이라 처음과 끝은 인접하므로 경우를 나눠서 생각했다.

 

1. 끝을 생각하지 않는 경우 : 1 번 부터 차례대로 인접하지 않고 N-1 번으로 갈 때 훔칠 수 있는 돈의 최댓값

2. 처음을 생각하지 않는 경우 : 2 번 부터 차례대로 인접하지 않고 N 번으로 갈 때 훔칠 수 있는 돈의 최댓값

 

동적 계획법으로 구현하여 1, 2 중 최댓값을 반환하면 된다.

 

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

print(solution([1, 2, 3, 1])) # 4