이번 문제는 주어진 조건대로 백트레킹을 진행하며 모든 경우를 구하고, 그 중 가장 큰 경우를 구하는 방식으로 해결하였다. x-1, x+1 인덱스의 원소의 곱을 에너지로 더하기 위해서 구슬 리스트를 지우기 전에 해당 값들을 미리 저장하고, x위치의 원소를 지운 후, 재귀 호출 하였고, insert함수를 이용하여 원래대로 구슬 리스트를 돌려놓았다.

• n을 입력받는다.
• 구슬 리스트 marbles를 입력받는다.
• 결과 변수 energy를 0으로 선언한다.
• 최대 에너지를 구하는 함수 get_energy를 cnt, e를 인자로 갖도록 선언한다.
  -> energy를 global로 선언한다.
  -> 만약 cnt가 n-2일 경우,
  --> energy를 energy와 e 중 더 큰 값으로 갱신한다.
  --> 함수를 종료한다.
  -> 1부터 marbles의 길이-1까지 반복하는 i에 대한 for문을 돌린다.
  --> tmp_e에 marbles[i-1]*marbles[i+1]를 저장한다.
  --> tmp에 marbles.pop(i)의 값을 저장한다.
  --> get_energy(cnt+1, e+tmp_e)를 재귀 호출한다.
  --> marbles의 i 인덱스에 tmp를 넣어준다.
• get_energy(0, 0)을 호출한다.
• energy를 출력한다.

Code

n=int(input())
marbles=list(map(int, input().split()))
energy=0
def get_energy(cnt, e):
    global energy
    if cnt==n-2:
        energy=max(energy, e)
        return
    for i in range(1, len(marbles)-1):
        tmp_e=marbles[i-1]*marbles[i+1]
        tmp=marbles.pop(i)
        get_energy(cnt+1, e+tmp_e)
        marbles.insert(i, tmp)
get_energy(0, 0)
print(energy)