프로그래머스|도둑질

문제 설명

배열의 앞에서부터 탐색하며 수를 더해서 합을 구하려고 합니다. 이때 연속된 칸에 있는 값은 가질 수 없고 마지막 원소와 첫 번째 원소는 연속되어 있다고 가정합니다. 이때 구할 수 있는 합의 최댓값을 출력하는 문제입니다.

작동 순서

1. 만약 배열의 길이가 1이라면 해당 배열의 원소값이 구할 수 있는 최댓값이므로 출력하고 프로그램을 종료합니다.
2. 각 위치 별로 해당 위치에서 가질 수 없는 최댓값을 저장할 배열을 생성합니다.
3. 각 위치별로 해당 위치에서 가질 수 없는 최댓값을 저장하기 전에 생각해야 할 것이 맨 앞의 원소와 맨 뒤의 원소는 연속되어 있으므로 둘 다 가질 수는 없습니다. 그렇기 때문에 맨 앞의 원소를 가지고 맨 뒤의 원소를 버리는 경우, 맨 앞의 원소를 버리고 맨 뒤의 원소를 가지는 경우 2가지로 나누어서 계산을 수행합니다.
4. 맨 앞의 원소를 가지고 맨 뒤의 원소를 버리는 경우를 계산하기 위해 계산 범위를 0~마지막-1까지로 지정하고 계산해줍니다. 계산 방법은 (직전 칸까지의 최댓값)과 (2칸 전까지의 최댓값+현재 칸의 값) 중 큰 값을 가지는 것입니다.
5. 맨 앞의 원소를 버리고 맨 뒤의 원소를 가지는 경우를 계산하기 위해서는 계산 범위를 1~마지막까지로 지정하고 계산해줍니다. 계산 방법은 4와 동일합니다.
6. 맨 앞의 원소를 가진 경우와 맨 뒤의 원소를 가지는 경우, 두 가지의 경우에서 얻을 수 있는 합 중 더 큰 값을 출력합니다.

소스코드

def solution(money):
    answer = 0
    totalmoney = len(money)
    
    if totalmoney==1:
        return money[0]
    
    dp=[0 for _ in range(totalmoney)]
    
    for i in range(0, totalmoney-1):
        if i==0:
            dp[i]=money[i]
        elif i==1:
            dp[i]=max(dp[i-1], money[i])
        else:
            dp[i]=max(dp[i-2]+money[i], dp[i-1])
    answer=dp[totalmoney-2]
    
    for i in range(totalmoney):
        dp[i]=0
    
    for i in range(1, totalmoney):
        if i==1:
            dp[i]=money[i]
        else:
            dp[i]=max(dp[i-2]+money[i], dp[i-1])
    if answer<dp[totalmoney-1]:
        answer=dp[totalmoney-1]
    return answer