[Baekjoon/Python] 16198 에너지 모으기

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

16198번: 에너지 모으기

처음 문제를 봤을 때 그리디로 접근해도 될 것 같았다.
각 단계에서 얻을 수 있는 최대 값을 구해서 구슬이 2개만 남았을 때 그 값들을 모두 합하려고 했다.

N = int(input())
li = list(map(int, input().split()))
ans = 0
while len(li)!=2:
    power = []
    for i in range(1,len(li)-1):
        power.append(li[i-1] * li[i+1])
    ans += max(power)
    idx = power.index(max(power))
    del li[idx+1]
print(ans)

하지만 시간초과도 아니고 바로 틀렸다고 한다..ㅎ

테스트케이스 다 맞았길래 이렇게 푸는 거구나 싶었지만 빨간불이 떠서 당황했다.

---

이번에는 백트래킹으로 방식을 바꿔서 생각해 봤다.
1. 구슬이 2개가 남을 때까지 재귀
2. 구슬이 2개가 되면 최댓값으로 초기화
3. 구슬이 3개 이상인 경우 재귀적으로 탐색해서 가장 큰 에너지 탐색

input = __import__('sys').stdin.readline
N = int(input())
li = list(map(int, input().split()))
ans = 0
def choose(val):
    global ans
    if len(li) == 2:
        if ans < val:
            ans = val
            return 0
    for i in range(1,len(li)-1):
        val += li[i-1] * li[i+1]
        tmp = li[i]
        del li[i]
        choose(val)
        li.insert(i,tmp)
        val -= (li[i-1]*li[i+1])

choose(0)
print(ans)

이렇게 하니 정답!