[BOJ] 11399번: ATM (C++)

0. 문제

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

 

각 사람이 돈을 인출 완료하는데 필요한 시간은 (대기 시간) + (해당 사람의 인출 소요 시간)이다. 이 시간의 합이 최소가 되도록 최적화하는 문제이다.

 

용어 정리를 하자면,

(인출을 완료하는데 필요한 시간)은 문제에서 묻는  (대기 시간) + (해당 사람의 인출 소요 시간)이고,

(인출 소요 시간)은 문제에서 입력으로 주어지는, 각 사람이 대기를 마치고 나서부터 ATM에서 돈을 인출 완료하기까지, 순수하게 돈을 뽑는데 걸리는 시간이다.

 

1. 아이디어

(대기 시간) + (해당 사람의 인출 소요 시간) 식을 보고 OS 스케줄링 기법을 연상했다.

스케줄링 기법 평가 지표에서 Turnaround time은 (Completion Time) - (Arrival Time)이다. 이 문제에 적용해보면, (대기 시간) + (해당 사람의 인출 소요 시간)은 Completion Time과 같고, 처음부터 모든 사람이 대기하므로 Arrival Time은 모두 0이다. 즉 Turnaround Time과 문제에서 요구하는 시간은 동일하다.

Turnaround Time은 각 프로세스가 실행되지 않는 대기 시간에 큰 영향을 받기 때문에, 이를 줄이는 것이 중요하다.

Turnaround Time에 대하여 Optimal한 스케줄링 방식은 Shortest Job First(SJF)이다. SJF는 가장 실행 시간이 짧은 프로세스를 먼저 실행하는 방식으로, 그리디 알고리즘의 범주에 속한다고 할 수 있다. 이 스케줄링 기법을 따라 풀이를 작성했다.

 

2. 풀이

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

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

  int n;
  std::cin >> n;
  std::vector<int> v(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> v[i];
  }
  std::sort(v.begin(), v.end());
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum += v[i] * (n - i);
  }
  std::cout << sum;
}

각 사람의 인출 소요시간 입력을 오름차순으로 정렬하여, 맨 앞 사람부터 인출하도록 시간을 계산한다. 각 사람이 인출을 완료하는데 필요한 시간은 앞 사람들 인출 소요 시간의 합이므로, 이를 모두 더해서 출력한다.

for문 내에서 sum을 계산하는 식이 Pi * (N - i)인 이유는, 전체 시간을 더했을 때 각 Pi가 N - i번 더해지기 때문이다. N=3에서 0번 사람은 P0만큼 필요하고, 1번은 P0 + P1, 2번은 P0 + P1 + P2만큼 필요하다. 각 Pi가 N - i번 더해지는 것을 확인할 수 있다.