[백준] 16198번 에너지 모으기 - Python / 알고리즘 중급 1/3 - 브루트 포스 - 재귀 (연습)

---

---

---

💡 문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 W$_i$이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. W$_{x-1}$ × W$_{x+1}$의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W$_1$, W$_2$, ..., W$_N$을 공백으로 구분해 주어진다. (1 ≤ W$_i$ ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

---

💭 접근

먼저 이 문제를 해결하기 위해 주어진 n개의 구슬 중 n - 2 개의 구슬의 인덱스로 순열을 만든다.
(첫번째와 마지막 숫자는 삭제할 수 없으므로)

이때, 만들어진 순열은 입력으로 주어진 숫자의 제거 순서이다.

따라서 이 인덱스의 순서에 따라 그 인덱스에 해당하는 숫자를 0으로 만든 뒤, 오른쪽 왼쪽에 처음으로 등장하는 0이 아닌 수를 뽑아 곱하여 정답에 더해준다.

예를 들어 주어진 예제 2번을 통해 문제 풀이 방법을 알아보자.

예제 2번 100 2 1 3 100
100 2 1 3 100 -> sum = 0
100 0 1 3 100 -> 100 x 1 = 100, sum = 100
100 0 0 3 100 -> 100 x 3 = 300, sum = 100 + 300 = 400
100 0 0 0 100 -> 100 x 100 = 10000, sum = 400 + 10000 = 10400

---

📒 코드

def dfs(depth):
    global ans

    if depth == n - 2:
        ans = max(ans, check_sum())
        return
    
    for i in range(len(x)):
        if x[i] not in perm:
            perm.append(x[i])
            dfs(depth + 1)
            perm.pop()

def check_sum():
    tmp = w[:]
    result = 0

    for idx in perm:
        tmp[idx] = 0

        for prev_idx in range(idx - 1, -1, -1):
            if tmp[prev_idx] != 0:
                prev_x = tmp[prev_idx]
                break

        for next_idx in range(idx + 1, n):
            if tmp[next_idx] != 0:
                next_x = tmp[next_idx]
                break
        
        result += prev_x * next_x
    return result

n = int(input())
w = list(map(int, input().split()))
x = [i for i in range(1, n - 1)]

ans = 0
perm = []
dfs(0)

print(ans)

---

💭 후기

순열을 사용하는 방법을 떠올렸다면 쉽게 해결할 수 있는 문제.

---

🔗 문제 출처

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

---