[백준/C++] 11399번: ATM

11399번: ATM 문제 바로가기

문제 분석

사람 수 N이 주어지고, 각 사람마다 돈을 인출하는데 걸리는 시간 P가 주어질 때,

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력하는 문제

이 때, 다른 사람이 돈을 인출하고 있는 경우에는 기다렸다가 인출해야 한다.

---

문제 풀이 과정

n번째 사람이 돈을 인출하는데 걸리는 시간을 생각해보면,

무조건 n-1번째까지의 사람들의 인출하는데 걸리는 시간을 다 더하고 자신의 시간까지 더해야 한다.

💡 그렇다면, 오름차순으로 정렬하는데 당연히 최솟값이 되겠구나 !

1. 입력받은 인출 시간 P값 오름차순 정렬
2. P[i] += P[i-1] 해주면서 합 저장
3. 결과값 ans += P[i] 으로 답 구하기

→ 결론적으로 모든 시간의 합의 최솟값을 구할 수 있다.

---

코드

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

int N, ans;
vector<int> P;

int main() {
    cin >> N;
    for (int i = 0, p; i < N; i++) {
        cin >> p;
        P.push_back(p);
    }
    sort(P.begin(), P.end());
    
    ans = P[0];
    for (int i = 1; i < N; i++) {
        P[i] += P[i-1];
        ans += P[i];
    }
    
    cout << ans;
    
    return 0;
}