[백준(파이썬/Python)] 16198_에너지 모으기

https://www.acmicpc.net/problem/16198

16198번: 에너지 모으기

 

문제에서 N값이 10이하로 매우 작기 때문에, 재귀 함수를 통해 모든 경우의 수에 대한 완전 탐색을 해주면 됩니다. 

 

완전 탐색을 하기 위해서는 현재 구슬 중에서 i번째 구슬을 선택했을 때 그 구슬을 제외한 리스트에서 다시 임의의 i번째를 선택하는 식으로 진행해야 합니다. 이를 위해 반복문 안에서 재귀함수를 호출하는 형식으로 구현했습니다.

 

문제에서는 copy 라이브러리를 이용하였는데, pop()과 copy.deepcopy()를 이용하는 대신에 선택한 원소를 제외하는 리스트 슬라이싱 방식으로 구현해도 될 것 같습니다.

 

그리고 제가 푼 방식에서는 backTracking() 함수를 이용했는데 사실 이 문제에서는 백트랙킹 기법을 사용하진 않았고, 모든 경우에 대해 탐색을 하였습니다. 중간에 가지치기를 할 부분이 마땅히 없다고 생각했기 때문입니다.

 

[풀이]

import copy

def backTracking(marble, x, energy):
    global answer
    energy += marble[x-1] * marble[x+1]
    marble.pop(x)

    # 구슬의 개수가 2개 남으면 선택 종료
    if len(marble) == 2:
        if energy > answer:
            answer = energy
        return

    for i in range(1, len(marble)-1):
        temp = copy.deepcopy(marble)
        backTracking(temp, i, energy)

n = int(input())
weight = list(map(int, input().split()))
answer = 0

# 구슬을 선택하는 모든 경우의 수를 다 해본다.
for i in range(1, len(weight)-1):
    temp = copy.deepcopy(weight)
    backTracking(temp, i, 0)

print(answer)