[파이썬][백준 16198][백트래킹] 에너지 모으기 - 컴도리돌이

16198번: 에너지 모으기

---

풀이 과정

1. 주어진 n의 개수가 너무나 작기 때문에 모든 경우의 수를 구해주면 된다. 

2. i번째를 삭제할 경우의 현재 에너지양 + w[i-1] * w[i+1], i번째를 제외한 w 배열, depth - 1로 탐색을 한다.

3. depth 가 3일 될 경우 경우의 수가 배열의 맨앞의 에너지 값 * 배열의 마지막 에너지 값만 계산 할 수 있기 때문에 해당 값과 현재 에너지를 더해서 반환해준다.

4. 가장 큰 값을 반환해준다.

---

풀이 코드

import sys; input = sys.stdin.readline
n = int(input())
W = list(map(int,input().split()))

def dfs(sum,w,depth) :
  if depth == 3 :
    return sum + (w[0] * w[-1])
  ret = sum
  for i in range(1,depth-1) :
    ret = max(ret,dfs(sum + w[i-1] * w[i+1],w[0:i] + w[i+1:],depth - 1))
  return ret

print(dfs(0,W,n))