백준 온라인 저지 (BOJ) 16198 에너지 모으기

문제

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

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

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

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

입력

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

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

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

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include<stdio.h> #include<stdbool.h> #pragma warning(disable:4996) #pragma warning(disable:6031) int n, size = 0, ans = 0; int ball[11], w[11], temp_w[11]; bool check[11]; void permutation(); void get_energy(); void copy(); int main() {     scanf("%d", &n);     for (int i = 1; i <= n; i++)         scanf("%d", &w[i]);     permutation();     printf("%d\n", ans);     return 0; } void permutation() {     if (size == n - 2) {         for (int i = 1; i <= n - 2; i++)         get_energy();         return;     }     for (int i = 2; i <= n - 1; i++) {         if (!check[i]) {             ball[++size] = i;             check[i] = true;             permutation();             check[i] = false;             size--;         }     } } void get_energy() {     int sum = 0, left = 1, right = 1;     copy();     for (int i = 1; i <= n - 2; i++) {         for (int j = ball[i] + 1; j <= n; j++) {             if (temp_w[j]) {                 right = temp_w[j];                 break;             }         }         for (int j = ball[i] - 1; j >= 1; j--) {             if (temp_w[j]) {                 left = temp_w[j];                 break;             }         }         sum += left * right;         temp_w[ball[i]] = 0;     }     if (sum > ans)ans = sum; } void copy() {     for (int i = 0; i <= 10; i++)         temp_w[i] = w[i]; } Colored by Color Scripter

cs

 

모든 경우를 다 따져서 풀었는데 너무 비효율적인 것 같다.