BOJ 16198 · 에너지 모으기

알고리즘 분류 : 브루트 포스  

재귀 함수를 이용하여 모든 경우의 수를 구하고, 그중에서 최댓값을 구하면 된다.

• 에너지 구슬을 사용하면 그 에너지 구슬은 더 이상 사용하지 않기 때문에, 사용 여부를 확인할 check 배열을 만든다.
• 에너지 구슬을 고를 때, 첫 번째 구슬과 마지막 구슬은 사용하지 않으므로 인덱스의 범위를 앞뒤로 1씩 줄인다.
• 양옆의 구슬을 이용하여 에너지를 모을 때, 이전에 사용된 구슬인지 확인해야 한다.
• 왼쪽이 사용된 구슬이라면 사용하지 않은 구슬이 나올 때까지 왼쪽으로 간다. 오른쪽은 반대로 확인한다.
• 사용한 구슬의 개수가 N-2개라면 에너지의 양이 최댓값인지 확인한다.

---

C++ 소스코드

#include <cstdio>

int n, ans;
int w[10];
bool check[10];

void solve(int cnt, int sums) {
    if (cnt == n-2) {
        if (ans < sums) ans = sums;
        return;
    }
    for (int i=1; i<n-1; i++) {
        if (!check[i]) {
            int left = i-1, right = i+1;
            while (check[left] && left > 0) left--;
            while (check[right] && right < n-1) right++;
            check[i] = true;
            solve(cnt+1, sums+(w[left]*w[right]));
            check[i] = false;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &w[i]);
    solve(0, 0);
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n = int(input())
w = list(map(int, input().split()))
check = [False]*n
ans = 0

def solve(cnt, sums):
    global ans
    if cnt == n-2:
        if ans < sums:
            ans = sums
        return
    for i in range(1, n-1):
        if check[i] is False:
            left, right = i-1, i+1
            while check[left] and left > 0:
                left -= 1
            while check[right] and right < n-1:
                right += 1
            check[i] = True
            solve(cnt+1, sums+(w[left]*w[right]))
            check[i] = False

solve(0, 0)
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 16198