[Brute Force] 백준 16198 : 에너지 모으기 - Python 파이썬

 

 

생각하기

브루트 포스를 통해 모든 경우를 다 살펴보고 최댓값을 구할 수 있을 지 생각해보았다

양쪽 끝에 있는 요소들을 고르지 않고 사이에 있는 것들만 recursive 메소드를 통해서 골라간다

 

시간복잡도

N의 최대가 10이기 때문에 양쪽 끝의 요소들을 고려하지 않고 사이의 것들만 선택하면

8 x 7 x 6 ..... x 2 x 1 이 된다.

8! = 40320 < 1억 이기 때문에 충분히 브루트포스를 통해 구할 수 있는 문제이다

 

이러한 구조로 진행되기 때문에 recursive 메소드 단계마다 리스트들을 새로 생성하여 기존의 리스트에서 선택된 요소가 빠진 리스트들 파라미터로 전달한다

 

구현하기

• 마지막 단계 : 파라미터로 넘어온 리스트의 길이가 2인 경우 (양쪽 끝 요소만 남은 경우) -> 에너지의 최대값을 측정
• index 1 부터 리스트 길이-2 (양쪽 끝 요소 사이의 요소들)을 하나씩 선택하여 에너지 계산 후 recursive 메소드 진행

파이썬의 경우 리스트를 얕은 복사를 하게 되면 새 변수의 참조가 기존 리스트를 참조하기 때문에 원본이 지속 바뀌어서 에러난다

따라서 copy 패키지의 deepcopy를 사용하여 깊은 복사를 해준다

 

import copy

new_array = copy.deepcopy(array)

 

import sys
import copy
input = sys.stdin.readline

N = int(input())

data = list(map(int, input().split()))

max_energy = 0

def search(array, energy):
    global max_energy
    n = len(array)

    if n == 2:
        max_energy = max(energy, max_energy)
        return

    for i in range(1, n-1):
        new_array = copy.deepcopy(array)
        new_add_energy = new_array[i-1] * new_array[i+1]
        del new_array[i]
        search(new_array, energy+new_add_energy)

search(data, 0)
print(max_energy)