백준 11399 - ATM

1. 문제 정리
  - N명의 사람과 각 사람의 인출하는데 걸리는 시간 Pi가 주어진다.

  - 한번에 한명만 인출이 가능하며, 그 외의 사람은 기다려야 한다.

  - 각 사람들의 (기다리는 시간+인출하는 시간)의 합이 최소가 되도록 한다.
 
2. 접근
  - 그리디 알고리즘으로 풀 수 있다.

  - 뒷 사람의 기다리는 시간을 짧게 한다 = 그 앞의 사람의 인출 시간을 짧게 한다. 로 볼 수 있다.

  - 즉, 인출 시간이 가장 빠른 사람을 앞으로, 가장 느린 사람을 뒤로, 즉 오름차순으로 정렬하여 순서대로 인출시킨다.

  - 앞에서 풀었던, (백준 1931 - 희의실 배정) 문제와 유사하다.
 
3. 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
vector<int> p;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        p.push_back(input);
    }

    sort(p.begin(), p.end());

    int waitT = 0;
    int ans = 0;
    for(int i: p){
        waitT = i+waitT;
        ans += waitT;
    }

    cout << ans;
}

  - int waitT : 각 순간의 대기자의 대기 시간과 인출 시간의 합을 저장한다.

  - int ans : 소요시간의 합을 저장한다.
 
4. 소감

  난이도가 어려운 문제는 아니었다. 이런 문제가 그리디 알고리즘으로 푸는 문제구나 라고 감을 잡을 수 있는 풀기 편한 난이도의 문제였다고 생각한다. 그리디 알고리즘을 처음 접한다면 이 정도 수준의 문제로 익숙해져 나가는 것도 좋을 거라 생각한다.