https://www.acmicpc.net/problem/14241

문제

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

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 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

Solution

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<int> Q;
    int N;
    int score = 0;
    cin >> N;
    for(int i = 0; i < N; i++){
        int input;
        cin >> input;
        Q.push(input);
    }

    while(Q.size() > 1){
        int first = Q.front();
        Q.pop();
        int second = Q.front();
        Q.pop();
        score += first * second;
        Q.push(first + second);
    }
    cout << score << '\n';
}

큐를 잘 활용해야 하는 문제.
큐에 있는 데이터가 총 하나 남을 때 까지 위에 있는 두개를 꺼내서 합쳐서 다시 계속 집어넣으면 된다.

가끔 BOJ의 문제 레벨을 보고있으면 구현이 빡세다 보단, 해당 지식을 모르면 못 푼다가 더 가까운 것 같다. 오히려 개인적으론 빡구현 문제가 더 어렵다.