[Baekjoon] 에너지 모으기

👀 문제 설명

문제

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

4

1 2 3 4

 

예제 출력 1

12

 

예제 입력 2

5

100 2 1 3 100

 

예제 출력 2

10400

 

예제 입력 3

7

2 2 7 6 90 5 9

 

예제 출력 3

1818

 

예제 입력 4

10

1 1 1 1 1 1 1 1 1 1

 

예제 출력 4

8

 

✍🏻풀이

재귀를 사용해 푸는 문제이다.

vector에 공들의 에너지값을 저장해둔다.

선택한 위치의 에너지값을 저장해두고, 그 공을 기준으로 왼쪽, 오른쪽에 있는 공들의 에너지를 곱한걸 더한다.

해당 공을 vector에서 빼고, 재귀를 사용해 그 상태에서 함수를 더 들어간다.

함수는 vector에 저장된 공의 개수가 2개라면 에너지값을 현재 max값과 비교하고, return해서 함수를 끝낸다.

함수가 끝나고 나왔으면, 해당 공을 다시 vector에 넣고, 앞에서 더한 왼쪽, 오른쪽에 있는 공들의 에너지를 곱한걸 sum에서 뺀다.

-> 이 과정을 for문을 사용해 반복한다. (기준 공을 선택하는 for문)

 

[참고]

https://nim-code.tistory.com/100

https://yabmoons.tistory.com/67

 

코드

//  에너지 모으기 (https://www.acmicpc.net/problem/16198)

#include <iostream>
#include <vector>

#define MAX 1000

using namespace std;

int N;
vector<int> W;
int maxW = -1;

void getMax(int sum) {
    if (W.size() == 3) { // 구슬이 3개 남은 경우
        sum += W.at(0) * W.at(2);
        maxW = max(maxW, sum);

        return;
    }

    for (int i = 1; i < W.size() - 1; i++) {
        int remove = W.at(i);
        sum += W.at(i - 1) * W.at(i + 1);
        W.erase(W.begin() + i); // i번째 값 삭제
        getMax(sum);
        W.insert(W.begin() + i, remove);
        sum -= W.at(i - 1) * W.at(i + 1); // i번째 값 다시 넣기
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    // input
    cin >> N;
    W.resize(N);
    for (int i = 0; i < W.size(); i++) {
        cin >> W.at(i);
    }

    getMax(0);
    cout << maxW << "\n";

    return 0;
}