백준 11399번 - ATM 문제 C++ [그리디 알고리즘]

📍 백준 11399번 - ATM 문제 C++ [그리디 알고리즘]

---

🧩문제 요약

<그리디 알고리즘>

n명의 사람이 주어진다. 

각 사람이 ATM기에서 돈을 인출하는 시간이 주어질 때 n명의 사람이 모두 돈을 인출할 수 있는 최소한의 시간을 구해라. 

---

🧾내가 작성한 초기 코드 

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

int main(){
    int n, i, time=0,sum=0, tmp ;
    vector<int> arr ; 
    cin >> n;
    for(i = 0; i<n ; i++){
        cin >> tmp; 
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    for(i=0;i<n;i++){
        sum += arr[i];
        time += sum; 
    }
    cout << time << "\n";
}

---

👍이 문제에서 배운점

 

😕 문제점 1. 

지금의 코드 보다 더 효율적인 방법은 없을까? 

 

 

✅ 각사람의 시간이 몇명한테 영향을 주는지 생각해 보기 

 첫 번째 사람은 뒷사람 n-1명에게 arr[0]만큼의 시간을 소비하게 만든다.

자신이 돈을 인출하는데 걸리는 시간 + 뒷사람 n-1명이 기다리는데 걸리는 시간이 소요되므로

👉 arr[0] + arr[0]*(n-1) = arr[0]*n 만큼의 시간이 걸리게 된다.

 

두 번째 사람은 뒷사람 n-2명이  arr[1]만큼의 시간을 소비하게 만든다.

👉 arr[1] + arr[1]*(n-2) = arr[1]*(n-1) 만큼의 시간이 소요된다.

 

n번째 사람은 자기 자신만 시간이 소요되므로 arr[n-1]만큼의 시간이 소요된다.

 

따라서 1 ~ n번째 사람이 걸리는 시간들을 다 더해주면 ans += arr[i]*(n-i) (i는 0부터 n-1까지) 가 된다.

 

---

🧾 완성된 코드 

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

int main(){
    int n, i, time=0, tmp ;
    vector<int> arr ; 
    cin >> n;
    for(i = 0; i<n ; i++){
        cin >> tmp; 
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    for(i=0;i<n;i++){
        time += arr[i]*(n-i);
    }
    cout << time << "\n";
}