[백준] 11399번: ATM

11399번: ATM

 

ATM 문제도 전형적인 그리디 문제 중 하나입니다.

 

앞에서부터 누적된 합을 답에 더해줘야 하기 때문에, 누적되는 합이 최소가 되도록 정렬해야 합니다.

그러기 위해선 더 적은 시간이 소요되는 사람을 우선시하여 정렬을 진행하고 누적으로 소요되는 시간들을 더해주면 됩니다.

 

그 값들을 모두 더하면 최소 시간이 걸립니다.

 

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

int N;
int ans;
vector<int> waitingTime;

void input() {
  cin >> N;
  waitingTime.resize(N);

  for (int i = 0; i < N; i++) {
    cin >> waitingTime[i];
  }
}

void calculate() {
  sort(waitingTime.begin(), waitingTime.end());

  ans = 0;
  int sum = 0;

  for (int i = 0; i < N; i++) {
    sum += waitingTime[i];
    ans = ans + sum;
  }
}

void printAnswer() {
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);

  input();
  calculate();
  printAnswer();

  return 0;
}