[백준 11399] ATM

문제

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

11399번: ATM

 

 

문제 분석

입력 받은 수의 사람들이 현금을 인출하는데 걸리는 시간을 입력 받는다. 

 

만약 { 4, 6, 2, 8, 1 }이 입력 받게 되면

 

첫번째 사람은 4분 후 현금을 뽑을 수 있고, 두번째 사람은 앞사람도 기다려야 하기에 10분, 그렇게 12, 20, 21 분의 시간을 기다리게 된다. 그럼 모두가 기다린 시간을 총 합치면 67분을 기다리게 된다. 

 

그럼 { 1, 2, 4, 6, 8 } 순으로 인출한다면? 

 

1, 3, 7, 13, 21로 총 45분이 걸린다. 

 

이처럼 최대한 적은 시간으로 인출 하였을떄 걸리는 시간을 출력하는 문제이다. 

 

 

알고리즘 설계

priority_queue를 사용하여 입력 받은 값을 적은 값부터 정렬 시킨다. 

 

이후 priority_queue가 비어 있지 않다면 돌아가는 반복문을 만들어준다.

 

priority_queue  가장 위에 있는 값을 앞 사람이 얼마나 시간이 걸렸는지 알려주는 변수에 더해주고, 그 변수를 다시 출력할 변수에 더해준다. 

 

그리고 priority_queue의 가장 위의 값을 없애준다. 

 

 

유의점

알고리즘 설계 단계에서 너무 단순하게 생각하면 안 된다. 

priority_queue의 정렬 방식을 한번 더 생각하자 

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int loop, input, container = 0, answer = 0;
    priority_queue<int, vector<int>, greater<>> pq;
    cin >> loop;

    while (loop--)
    {
        cin >> input;
        pq.push(input);
    }

    while (!pq.empty())
    {
        int front = pq.top();
        pq.pop();

        container += front;
        answer += container;
    }

    cout << answer;
}