[BOJ:16198] 에너지 모으기

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

Note

문제를 처음에 접근했을 당시에는 예시 입출력들을 가지고 규칙을 찾아본 결과, 그리디 과정으로 규칙이 찾아져서 코드를 제출했더니 틀렸다. 내가 처음에 풀이한 그리디 과정은 문제의 조건에 따라 i 구슬을 제거할때 i-1,i+1의 에너지 구슬로 모은 에너지 값이 최대가 되는 구슬로 정하였다. 첫 번째 예시의 경우 [1,2,3,4]에서 3을 골랐을때 8(2*4)가 가장 크기 때문에 3을 제거해주고 남은 2를 제거해줄 때 에너지는 4가 되어 총 에너지 합은 12가 된다. [100,2,1,3,100]의 경우 100(2) (에너지(제거숫자)), 6(1), 100(3)에서 큰 값 100이 같은 경우 제거 숫자는 작은 경우, [100,1,3,100]에서 1제거, 이유는 에너지가 300이 가장 크기 때문. [100,3,100]은 3제거 10000에너지 획득. 총에너지는 10400으로 출력 에너지와 같다. 문제에서 주어진 다른 예시들도 그리디로 얻을 수 있는 가장 큰 에너지,제거되는 가장작은 숫자 기준으로 수를 제거하면 올바르게 나오지만 반례가 존재한다. 현재 구슬을 제거할 때 얻는 에너지가 가장크더라도, 현재 제거되는 숫자가 다음에서 얻을 에너지가 충분히 크다면 제거하면 안되는 반례가 존재한다. 구체적인 예시는 주어진 에너지 구슬이 다음과 같을때 [3,1,2,4,5] 위 알고리즘으로 에너지 총합을 구하면 구슬 4제거 에너지 10획득, [3,1,2,5] 구슬 1제거, 에너지 6획득, [1,2,5] 구슬 2제거 에너지 5획득. 총 에너지 31이다.

그러나 1,2,4 순으로 제거한다면 에너지는 6,12,15를 얻을 수 있어 총 33의 에너지를 얻을 수 있다. 즉 규칙을 발견하지 못하였고, N의 값이 최대 10정도밖에 되지 않기 때문에 재귀로 부르트포스를 구현하여 모든 경우의 수를 구하고 최대 에너지를 구했다.

Code

import sys

input = sys.stdin.readline

def DFS(total):
    global answer
    if len(nums) <= 2:
        answer = max(answer,total)
        return
    else:
        for i in range(1,len(nums)-1):
            weight = nums[i-1]*nums[i+1]
            temp = nums[i]
            nums.pop(i)
            DFS(total+weight)
            nums.insert(i,temp)

n = int(input())
nums = list(map(int,input().split()))

answer = 0
DFS(0)

print(answer)