16198: 에너지 모으기

• 평이한 brute force (dfs) 및 backtracking 문제
• dfs 함수에서 input parameter로 가독성을 위해 W를 넣어주기는 했다만, 실제로 list를 parameter로 넘겨줄 땐 값이 아니라 주소가 복사되니까 큰 의미는 없음
• 재귀적으로 함수가 호출될 때 어차피 함수는 메모리 공간에 stack 형식으로 쌓이니까 W가 global 변수여도 dfs 탐색 및 backtracking이 가능함

import sys

def dfs(depth, W, local_energy):
    global energy

    if depth == N-2:
        energy = max(energy, local_energy)
        return

    for i in range(1, len(W)-1):
        bef = W[i-1]; aft = W[i+1]
        tmp = W.pop(i)
        dfs(depth+1, W, local_energy + bef*aft)
        W.insert(i, tmp)


N = int(input())
W = list(map(int, sys.stdin.readline()[:-1].split()))

energy = 0
dfs(0, W, 0)
print(energy)