처음 문제를 봤을 때 그리디로 접근해도 될 것 같았다.
각 단계에서 얻을 수 있는 최대 값을 구해서 구슬이 2개만 남았을 때 그 값들을 모두 합하려고 했다.
N = int(input())
li = list(map(int, input().split()))
ans = 0
while len(li)!=2:
power = []
# tmp = [tmp.append(i) for i in li]
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)
이렇게 하니 정답!