[BOJ] 16198번 | 에너지 모으기 (C++)

🔗문제 보러가기

16198번: 에너지 모으기

 

🧑🏻‍💻풀이 과정

1. 에너지 값들을 vector<int> weights에 저장한 후, weights의 크기가 2가 될 때까지 다음 과정을 반복합니다.
   • 정답을 저장할 변수(maxEnegy)와 현재 경우의 수의 합계를 저장할 변수(sum)를 생성합니다.
   • weights를 i = 1부터  i = weights.size() - 1까지 for 문으로 순회합니다.
   • weights[i - 1] x weights[i + 1]의 값을 sum에 더합니다.
   • weights[i] 원소는 삭제합니다.
   • 더해진 sum 값과 함께 재귀로 호출합니다.
2. weights.size() == 2가 되었다면, maxEnegy = max(maxEnegy, sum)으로 갱신합니다.
3. 함수가 종료되었다면, 답을 출력합니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
using namespace std;

void Backtracking(vector<int>& weights, int& maxEnegy, int sum)
{
    if (weights.size() == 2)
    {
        maxEnegy = max(maxEnegy, sum);
        return;
    }

    for (int i = 1; i < weights.size() - 1; i++)
    {
        int element = weights[i];
        int addValue = weights[i - 1] * weights[i + 1];

        weights.erase(weights.begin() + i);
        Backtracking(weights, maxEnegy, sum + addValue);
        weights.emplace(weights.begin() + i, element);
    }
}

int GetMaxEnegy(vector<int>& weights)
{
    int answer = -1;
    Backtracking(weights, answer, 0);
    return answer;
}

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

    int N;
    cin >> N;

    vector<int> weights(N);
    for (int i = 0; i < N; i++)
        cin >> weights[i];

    int answer = GetMaxEnegy(weights);
    cout << answer;
    return 0;
}