[백준] 16198(파이썬) - 에너지 모으기
resilient
·2021. 7. 27. 11:42
728x90
반응형
https://www.acmicpc.net/problem/16198
- 이 문제는 일고나서 아 DFS로 풀어야겠다 라고 생각했다. 최대 입력값도 작고, 생각 해봤을 때, 한 경로로 깊이 들어가서 값을 저장하고, 또 다른 한 경로로 깊이 들어간 뒤 값을 저장해서 비교를 통해 갱신해가면서 풀면 된다고 생각했다.
- DFS로 방향을 잡은 뒤 부터는 수월했지만 문제 조건을 보면 data[i] 를 계산 뒤에 삭제 하라고 했는데, 삭제를 하고 DFS 재귀를 실행시켜준 뒤, 다른 경로의 DFS재귀함수를 위해 다시 원상 복구를 시켜놔야한다. 이 부분이 중요했다.
# 이문제는 DFS
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())
data = list(map(int,input().split()))
def dfs(num):
global Max
if len(data)==2:
if Max < num:
Max = num
return
for i in range(1,len(data)-1):
num += data[i-1]*data[i+1]
temp = data[i]
del data[i]
dfs(num)
# dfs함수 실행시켜주고 다른 dfs에 영향을 미치지 않기위해
# 원상복구 시켜준다.
data.insert(i,temp)
num -= data[i-1]*data[i+1]
Max = 0
dfs(0)
print(Max)
반응형
'자료구조 & 알고리즘 > 백준(Baekjoon)' 카테고리의 다른 글
[백준] 1182(파이썬) - 부분수열의 합 (0) | 2021.07.31 |
---|---|
[백준] 16926(파이썬) - 배열 돌리기 1 (0) | 2021.07.28 |
[백준] 14226(파이썬) - 이모티콘 (1) | 2021.07.26 |
[백준] 1987(파이썬) - 알파벳 (0) | 2021.07.25 |
[백준]11048(파이썬) - 이동하기 (0) | 2021.07.24 |