1. 문제 설명

에너지 모으기

2. 문제 분석

제거한 에너지 위치를 check로 비트 조정, 백트래킹한다.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
weights = list(map(int, sys.stdin.readline().rstrip().split()))
check = [False for _ in range(n)]
INF = sys.maxsize
answer = -INF

def valid_adjacent(idx):
    added = 0
    for i in range(idx-1, -1, -1):
        if not check[i]:
            added = weights[i]
            break
    for i in range(idx+1, n):
        if not check[i]:
            added *= weights[i]
            break
    return added

def DFS(cnt, total):
    global answer
    if cnt == 2: answer = max(answer, total)

    for i in range(n):
        if not check[i] and i != 0 and i != n-1:
            check[i] = True
            DFS(cnt-1, total + valid_adjacent(i))
            check[i] = False

DFS(n, 0)
print(answer)