[백준] 16198번 : 에너지 모으기 (Small) (C++)

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)

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

// 16198. 에너지 모으기
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> vec;
int result = 0;
 
void recur(vector<int> _vec, int total)
{
    // 원소가 2개만 남았다면 return
    if (_vec.size() == 2)
    {
        result = max(result, total);
        return;
    }
 
    // 첫번째와 마지막 에너지 구슬은 고르지 않는다.
    for (int i = 1; i < _vec.size() - 1; i++)
    {
        // 새로운 배열 생성
        vector<int> temp;
        int t = 0;
        for (int j = 0; j < _vec.size(); j++)
        {
            // i번째 구슬을 선택했다면
            if (i == j)
            {
                // t에 (x - 1) x (x + 1)를 담는다.
                t = _vec[j - 1] * _vec[j + 1];
                continue;
            }
 
            // i번째 원소를 제외하고 배열에 담는다.
            temp.push_back(_vec[j]);
        }
 
        // 다음 재귀로 넘어간다.
        recur(temp, total + t);
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vec.resize(n, 0);
    for (int& ele : vec) cin >> ele;
 
    recur(vec, 0);
 
    cout << result;
 
    return 0;
}
 

 

---

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

16198번: 에너지 모으기