[0614] 알고리즘

11399. ATM

  문제 봐보다 어딘가 익숙해서 보니... 알고리즘 강의 들었을 때 기말고사 문제로 나왔던 문제였다. 그나마 이해할 수라도 있는 문제였었는데... 마침 자다 일어난 머리로도 풀 수 있을 것 같아서 풀었다.

 

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

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

  int n;
  int num;
  long long min = 0;
  std::vector<int> time;

  std::cin >> n;

  for (int i = 0; i < n; i++)
  {    
    std::cin >> num;
    time.push_back(num);
  }
  std::vector<long long> sum (n, 0);
  std::sort (time.begin(), time.end());

  sum[0] = time[0];
  min = sum[0];

  for (int i = 1; i < n; i++)
  {
    sum[i] = sum[i - 1] + time[i];
    min += sum[i];
  }  

  std::cout << min << '\n';

  return 0;
}

  그리디 알고리즘 문제. 입력받은 수들을 벡터로 저장하고 이 벡터를 algorithm의 sort를 이용해 정렬, 각 사람의 대기 시간을 구한다. 원래 2중 for문이 들어가 있었는데... 어차피 i-1번째 사람의 대기 시간에 i번째 사람의 인출 시간을 더하면 i번째 사람의 총 대기시간이 구해져서 코드를 더 간단히 만들 수 있었다.

 

  그리고 언제나 상기하고자 해도 놓치는 자료형 범위... 처음엔 모든 자료형을 int로 했다가 그래서는 문제에서 나올 수 있는 최대 수들에 대해 크기가 모자랄 수 있음을 알아내고 long long으로 바꿨다. 입력 범위와 조건을 잘 살펴보고 범위를 따지는 버릇을 들여야겠다.

 

  그리고 알고리즘 헤더파일... 편하다 최고