16198번: 에너지 모으기 파이썬

유형은 백트래킹

N = int(input())
arr = list(map(int,(input().split())))

result = 0

def dfs(v,c):

    global result
	# 배열이 두칸남았을 경우 
    # 맨왼쪽 오른쪽은 지울수없으므로 이렇게한다
	if N-2 == c:
        result = max(result,v)
        return
    
    for i in range(1,len(arr) - 1):
		# 지울 인덱스 번호 양옆을 곱을 구한다.
        value = arr[i-1] * arr[i+1]
        # 삭제한값을 다시 복구 하기위해 변수로 선언한다
        rollback = arr[i]
        # i번째에 있는 요소를 삭제한다.
        del arr[i]
        dfs(value+v,c+1)
        # 삭제한 요소를 다시 복구한다.
        arr.insert(i,rollback)

dfs(0,0)
print(result)