백준 14241번 슬라임 합치기 c++ 풀이

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

2
3 4

예제 출력 1 복사

12

예제 입력 2 복사

3
2 2 2

예제 출력 2 복사

12

예제 입력 3 복사

3
1 2 3

예제 출력 3 복사

11

예제 입력 4 복사

3
3 1 2

예제 출력 4 복사

11

 

 

간단하게 priority_queue를 이용해서 풀이했다.

#include <bits/stdc++.h>

using namespace std;


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

    int n;
    cin >> n;
    priority_queue<int> pq;

    for (int i = 0; i < n; i++) {
        int slime;
        cin >> slime;
        pq.push(slime);
    }

    int score = 0;

    while (pq.size() > 1) {

        int x = pq.top();
        pq.pop();
        int y = pq.top();
        pq.pop();

        int n = x + y;
        pq.push(n);
        score += x * y;

    }
    cout << score << "\n";


}