[백준 11399] ATM

ATM

문제설명

사람의 수를 입력받고, 사람당 걸리는 시간을 입력 받는다. 사람들이 돈을 인출하는데, 최소한의 시간 합을 구해서 출력시켜라.

---

알고리즘

1. 사람의 수와 각 사람당 걸리는 시간을 입력 받는다.
2. 걸리는 시간을 오름차순으로 정렬한다.
3. 반복문을 사용해서 각 사람이 걸리는 시간을 더해주고, 이전 사람이 걸렸던 시간까지 누적해서 더한다.
4. 결과를 출력한다.

---

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;    // 사람수 입력    
    vector <int> v;
    while (N)
    {
        int num;
        cin >> num;
        v.push_back(num);
        N--;
    }

    sort(v.begin(), v.end());//오름차순으로 정렬->빨리끝나는사람 먼저
    int sum = 0,temp=0;
    for (int i = 0; i < v.size(); i++)
    {
        sum = sum + temp+ v[i];//현재 순서의 사람이 걸리는 시간 연산
        temp += v[i];//다음 사람이 대기하는 시간을 위한 연산
    }
    cout << sum << "\n";//결과 출력

    return 0;
}

고찰

이번 문제는 greedy 알고리즘으로 각 사람당 걸리는 시간을 오름차순으로 정렬하여 최소 시간을 구했다. 시간이 짧은 순으로 정렬한 이유는 빨리 끝나는 사람이 먼저 끝내야 뒤에 대기하는 사람이 최소한으로 기다릴 수 있기 때문이다.
따라서 오름차순으로 정렬하고 각 사람당 기다린 시간을 구하기 위해서 시간의 합 외의 변수를 하나 더 선언해서 총 기다린 시간을 연산해서 총 시간을 구하도록 한다.