[PS] 프로그래머스 등굣길

프로그래머스 등굣길

문제 해결 아이디어)
dp이용. 주의사항은 원 모양이기 때문에 첫번째 집을 털면 마지막 집은 털 수 없다.
각각의 경우를 나누어 더 큰 쪽을 return

def solution(money):

    n = len(money)
    
    # 첫번째 O 마지막 X
    dp = [0]*n
    dp[0] = money[0]
    dp[1] = dp[0]
    for i in range(2, n-1):
        dp[i] = max(dp[i-1], dp[i-2]+money[i])
    dp[-1] = dp[-2]
        
    # 첫번째 X 마지막 O
    dp2 = [0]*n
    dp2[0] = 0
    dp2[1] = money[1]
    for j in range(2, n):
        dp2[j] = max(dp2[j-1], dp2[j-2]+money[j])
    
    return max(dp[-1], dp2[-1])