[백준/C++/Greedy] 11399 ATM

0. 문제

ATM / 실4 / 11399 / greedy

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

ATM 기기가 한 대 밖에 없는 상황이라

인출 시간이 각각 다른 유저들이 대기하고 있을 때 

모든 유저의 대기 시간 누적 합이 최소가 되도록 

ATM 기기 사용 순서를 정해야하는 문제이다

 

ATM 유저의 대기 시간의 총 누적합이 최소가 되려면

인출 시간이 적게 걸리는 유저부터 사용해야

최소가 될 수 있을 것이다

 

그런데 인풋 조건은 정렬 상태가 아닌 랜덤이므로

내가 정렬시켜야 한다

 

 

 

1. 테스트 케이스 분석

인풋 첫 줄에는 유저의 수가 주어지고

그 다음 줄에는 각 유저의 인출 시간이 주어진다

 

각 유저의 인출 시간 기준으로 오름차순 정렬한 후 

특정 유저 차례가 되면 

해당 유저부터 이후 순서의 모든 유저 대기시간에는

해당 유저의 인출 시간이 포함되도록 계산해야한다

 

각 유저의 대기 시간을 모두 더해서

모든 유저의 대기 시간 누적 합을 출력하면 된다

 

2. 코드 구상

제시된 인풋 값을 저장한 후 

다시 sort 함수로 오름차순 정렬을 하고 

루프를 돌며 해당 차례 유저의 인출 시간을 

해당 유저의 대기 시간부터 이후 순서의 유저들의 대기 시간에 모두 더해준다

 

각 유저들의 대기 시간의 합을 모두 더해

모든 유저 대기 시간 누적 합을 구하고 출력한다

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;  // 사람 수
    cin >> n;

    vector<int> withdraw(n);  // 각자 인출에 드는 시간 저장

    // 인출 시간
    for (int i = 0; i < n; i++) {
        cin >> withdraw[i];
    }

    // 오름차순 정렬
    sort(withdraw.begin(), withdraw.end());

    int total = 0;  // 모든 사람 소요 시간
    int wait = 0;   // 현재 사람까지의 대기 시간

    // 순서대로 계산
    for (int i = 0; i < n; i++) {
        wait += withdraw[i];  // 현재 사람 대기 시간
        total += wait;        // 모든 사람 대기 시간 합산
    }

    cout << total << endl;  // 모든 사람 대기 시간 합산
    return 0;
}