[백준] 16198 - 에너지 모으기

1. 문제

16198번: 에너지 모으기

2. 개요

백트래킹 활용 문제.

첫째, 마지막 구슬을 제외한 구슬을 선택 후 양 옆의 구슬의 에너지를 추가하고 선택한 구슬을 제거하는 작업을 반복했을 때 얻을 수 있는 에너지의 최댓값을 구하는 문제.

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())

W = list(map(int, sys.stdin.readline().split()))
ans = 0

def bt(idx = 0, l = []):
    if idx == N-2:
        calc(l)

    else:
        for i in range(1, N-1-idx):
            bt(idx + 1, l + [i])

def calc(lst):
    global ans
    tmp = 0
    tmpW = [w for w in W]
    for num in lst:
        tmp += tmpW[num-1] * tmpW[num+1]
        tmpW = tmpW[:num] + tmpW[num+1:]
        
    ans = max(ans, tmp)

bt()
print(ans)

백트래킹으로 모든 경우의 수를 찾는다.

이때 첫째와 마지막 구슬은 선택대상에서 제외되고, 선택한 구슬이 항상 빠지기 때문에 탈출조건은 idx == N-2 일때이며, for문의 범위도 1부터 N-1-idx로 잡는다.

백트래킹 재귀를 탈출했다면 완성된 리스트를 가지고 계산하여 최댓값을 갱신해나가면 된다.