[C++][BOJ/백준] 14241 슬라임 합치기

 

 

Baekjoon Online Judge

 

클릭 시 문제로 이동

 

 

[문제]

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

 

[입력]

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

 

 

[출력]

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

 

 

---

 

[코드]

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

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

    int N, res = 0;

    cin >> N;

    stack<int> s;

    for (int i = 0; i < N; i++)
    {
        int tmp;

        cin >> tmp;
        s.push(tmp);
    }

    while (s.size() > 1)
    {
        int x = s.top();
        s.pop();

        int y = s.top();
        s.pop();

        res += x * y;
        s.push(x + y);
    }

    cout << res << '\n';

    return 0;
}