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

문제

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

16198번: 에너지 모으기

설계

- 3개씩 묶어서 확인 하면서 1,3번째의 합이 가장 작은 경우의 수를 저장, 2번째 index를 제거한다.
- 위 과정을 반복하면서 리스트에 2개가 남을때 까지 반복한다.
- 전체 합계의 최대값을 구해야 함으로 dfs를 사용, while문으로 사용시 반례가 존재한다.

※ while문 사용시 반례

8
10 7 8 9 10 2 4 13

정답 : 612

def dfs(arr, sumV):
    global maxV
    if len(arr) <= 2:   # 구슬이 2개만 남을 경우 최대값 무게 확인
        maxV = max(maxV, sumV)
        return

    for i in range(len(arr) - 2):
        value = arr[i + 1]
        add = arr[i] * arr[i + 2]
        arr.pop(i + 1)
        dfs(arr, sumV + add)
        arr.insert(i + 1, value)    # inser를 활용해 arr을 원상복구 해준다.

N = int(input())
arr = list(map(int, input().split()))
maxV = 0
dfs(arr, 0)
print(maxV)