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

백준의 에너지모으기(16198) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 본인은 이 문제를 해결할 때 Vector를 사용하였다.

   문제에서 제시하는 방법을 Vector의 함수들을 이용한다면 쉽게 접근할 수 있다.

2. 먼저 사용된 Vector의 함수들에 대해서 설명해보자면

   V.at(a) = Vector에서 a번 Index의 값을 가져온다.

   V.erase(a) = Vector에서 a번 Index의 값을 삭제한다.

   V.insert(a, b) = a의 위치에 b값을 삽입한다.

   나는 이렇게 3개의 함수를 이용하여 구현하였다.

3. 위의 내용을 바탕으로 본격적인 문제를 풀어보자.

   첫 번째와 마지막 공을 제외한 공들 중에서 하나를 선택해서, 그 공을 없애버리고, 그 공을 기준으로 왼쪽 오른쪽의 있는

   공들의 에너지를 곱한게 에너지가 된다.

   이 문제에 경우, 뽑을 수 있는 모든 경우의수에 대해서 에너지를 계산해보면 된다.

4. 3의 이론을 2의 코드에 대입시켜보자.

   i번째 공을 선택한다. ==> V.at(i)

   i번째 공을 기준으로 왼쪽 오른쪽의 공의 에너지를 곱한다. ==> Energy = V.at(i-1) * V.at(i+1)

   i번째 공을 없애버린다. ==> V.erase(V.begin() + i)

   Vector의 경우, 위의 상황처럼 i번째 공을 없애버리면, 알아서 뒤에 있는 값들이 하나씩 앞으로 당겨진다.

   위의 코드를 통해서 공을 계속해서 뽑으면 되는데 언제까지 뽑는지 생각해봐야 한다.

   가장 첫번째 공과 마지막 공은 선택할 수 없다고 했으니, Vector의 size가 2가 되면 뽑을 수 있는 모든 공을 뽑았다는

   의미가 된다.

5. 4번과 같은 방식으로 계속해서 모든 경우의수를 구해주면 되는데, 이 때 주의 해야할 것이 공을 다시 원래대로

   복구시켜 놓아야 한다는 것이다.

   예를 들어 설명해보자면, 1 2 3 4 5 중에서 2 3 4 를 뽑았을 때의 에너지와 2 4 3을 뽑았을 때의 에너지는 다를 것이다.

   2 3 4를 뽑은 경우에는 (1 x 3) + (1 x 4) + (1 x 5) = 12가 되지만 2 4 3을 뽑은 경우에는 (1 x 3) + (3 x 5) + (1 x 5) = 23 이

   될 것이다.

   따라서 4번의 과정을 통해서 2 3 4의 공을 뽑는 과정을 완료했다면 아마 벡터에는 1 5 이렇게 2개의 값만 있을 것이다.

   다시 1 2 3 4 5 라는 원래의 상태로 만들어주고, 그 다음을 진행해야 정확한 계산이 이루어진다.

   그러기 위해서는 없앴던 공을 다시 넣어주는 과정이 있으면 된다.

   없앴던 i번째 공을 i번쨰에 집어넣는다. ==> V.insert(i, select)

   설명이 생각보다 어려워보일 수 있지만 코드를 본다면 쉬울 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
using namespace std;
 
int N, Max_Energy, Tmp_Energy;
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        V.push_back(a);
    }
}
 
void Select_Ball()
{
    if (V.size() == 2)
    {
        if (Max_Energy < Tmp_Energy) Max_Energy = Tmp_Energy;
        return;
    }
 
    for (int i = 1; i < V.size() - 1; i++)
    {
        int Select = V.at(i);
        Tmp_Energy = Tmp_Energy + V.at(i - 1) * V.at(i + 1);
        V.erase(V.begin() + i);
        Select_Ball();
        V.insert(V.begin() + i, Select);
        Tmp_Energy = Tmp_Energy - V.at(i - 1) * V.at(i + 1);
    }
}
 
void Solution()
{
    Select_Ball();
    cout << Max_Energy << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}