[백준] 16198(파이썬) - 에너지 모으기

https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

• 이 문제는 일고나서 아 DFS로 풀어야겠다 라고 생각했다. 최대 입력값도 작고, 생각 해봤을 때, 한 경로로 깊이 들어가서 값을 저장하고, 또 다른 한 경로로 깊이 들어간 뒤 값을 저장해서 비교를 통해 갱신해가면서 풀면 된다고 생각했다.
• DFS로 방향을 잡은 뒤 부터는 수월했지만 문제 조건을 보면 data[i] 를 계산 뒤에 삭제 하라고 했는데, 삭제를 하고 DFS 재귀를 실행시켜준 뒤, 다른 경로의 DFS재귀함수를 위해 다시 원상 복구를 시켜놔야한다. 이 부분이 중요했다.

# 이문제는 DFS


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())
data = list(map(int,input().split()))

def dfs(num):
    global Max
    if len(data)==2:
        if Max < num:
            Max = num
            return
    for i in range(1,len(data)-1):
        num += data[i-1]*data[i+1]
        temp = data[i]
        del data[i]
        dfs(num)
        # dfs함수 실행시켜주고 다른 dfs에 영향을 미치지 않기위해
        # 원상복구 시켜준다.
        data.insert(i,temp)
        num -= data[i-1]*data[i+1]
 
Max = 0
dfs(0)
print(Max)