백준 #16198 에너지 모으기

문제 링크

[16198 에너지 모으기]

문제 설명

$N$개의 구슬에 에너지가 부여되어있고 첫번째와 마지막 구슬을 제외한 나머지 구슬 중에서 하나씩 구슬을 고른다. 이때 선택된 구슬 양 사이드의 에너지가 서로 곱해져서 총 에너지에 더해지고 선택된 구슬은 제거된다. 이런식으로 구슬을 계속해서 골라나갈 때 총에너지의 최대값을 찾는 문제

코드

import sys
input = sys.stdin.readline


def solve(arr, energy):
    global max_v

    if len(arr) == 3:
        energy += (arr[0] * arr[2])
        if energy > max_v:
            max_v = energy
        return

    for i in range(1, len(arr) - 1):
        solve(arr[:i] + arr[i + 1:], energy + arr[i - 1] * arr[i + 1])

N = int(input())
ls = list(map(int, input().split()))
max_v = 0
solve(ls, 0)
print(max_v)

풀이

백트래킹으로 풀었다. $N$범위가 10까지밖에 안돼서 모든 경우를 다 봐도 시간이 넉넉했다!