에너지 모으기

문제

N개의 에너지 구슬이 일렬로 있고 에너지 구슬을 이용해서 에너지를 모으려고 합니다.
i번째 에너지 구슬의 무게는 W_i 입니다.
에너지를 모으는 방법은 다음과 같고 반복해서 사용가능합니다.
1. 에너지 구슬 하나를 고릅니다. 고른 에너지 구슬을 X라고 합니다. (첫번째, 마지막 제외)
2. X번째 에너지 구슬을 제거합니다.
3. W_x-1 X W_x+1의 에너지를 모을 수 있습니다.

제약조건
에너지 구슬의 개수 N (3<=N<=10)

풀이

구슬을 선택하는 순서에 따라 결과가 다릅니다.
함수를 다음과 같이 정의합니다 : 주어진 리스트에서 양 끝점을 제외한 구슬을 선택했을때 얻을 수 있는 에너지를 반환하는 함수.

이를 재귀로 표현하면

제가 정의한 함수가 자기 자신을 호출해서 정의가능하다는 사실을 알수있습니다.
주어진 리스트 길이가 2일 경우 양끝점은 제외한다는 조건에 의해서 어떤 구슬도 선택할 수 없으므로 0을 리턴합니다.

코드

'''
Created by jun on 21/05/26
'''
def dfs(marbles:list):
    if len(marbles) == 2:
        return 0
    return max(marbles[idx - 1] * marbles[idx + 1] + dfs(marbles[:idx] + marbles[idx + 1:])
               for idx in range(1, len(marbles)-1))

N = int(input())
marbles = list(map(int, input().split()))
print(dfs(marbles))

새로 알게된 사실

pop/push대신 인덱스 슬라이싱 이용.