백준 16198 에너지 모으기 -python
문제
- 브루트 포스 문제
문제풀이
- 구슬을 하나하나 순서대로 모두 뽑아서 그 중 최대 에너지 값을 리턴해준다
- 맨 앞구슬과 맨 뒤구슬이 남았을 때의 총합을 현재의 최대값(maxV)과 비교
- 재귀호출 전 선택한 구슬을 빼주고, 재귀호출 후 빼준 구슬을 다시 넣어준다
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def f(s):
global maxV
# 맨 앞구슬과 맨 뒤구슬만 남았을 때의 총합을 구해서 최대값 비교
if(len(arr) == 2):
if(s > maxV):
maxV = s
return
else:
for i in range(1,len(arr)-1):
# 선택한 구슬의 전, 후 값을 저장
r = arr[i-1] * arr[i+1]
temp = arr[i]
# 선택한 구슬 제거해주기
del arr[i]
f(s + r)
# 위에서 제거했던 구슬을 해당 위치에 다시 넣어주기
arr.insert(i, temp)
n = int(input())
arr = list(map(int, input().split()))
maxV = 0
f(0)
print(maxV)
