11399. ATM

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

11399번: ATM

풀이

아이디어

만약 인출하는데 시간이 오래 걸리는 사람이 먼저 들어가게 된다면 오랜 시간을 많은 사람들이 기다려야 하므로 각 사람이 돈을 인출하는데 필요한 시간이 모두 길어질 것이다.

하지만 인출하는데 시간이 오래 걸리는 사람이 뒤로 가게 된다면 오랜 시간을 기다려야 하는 사람의 수가 줄기 때문에 각 사람이 돈을 인출하는데 필요한 시간의 합이 줄어들게 된다.

따라서 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 만들기 위해서는 시간에 적게 걸리는 사람 부터 오래 걸리는 사람 순서대로 줄을 서야 한다.

문제가 그리디로 분류되어 있긴 한데 이게 그리디 알고리즘인지 잘 모르겠다. 그리디 알고리즘에 대해서 좀 더 확실하게 공부해봐야겠다...ㅎㅎ

코드

/*
2022-2-6
11399_ATM
https://www.acmicpc.net/problem/11399
*/

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

int N, T;
int ans = 0;
vector<int> waiting;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> T;
        waiting.push_back(T);
    }

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

    for(int i = 0; i < N; i++)
        ans += waiting[i] * (N - i);

    cout << ans;

    return (0);
}