[백준] 11399번: ATM

 

 

---

 

문제

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

 

 

개념

그리디 알고리즘, 정렬

 

 

실행 결과

 

 

 

 

구현 코드(c++)

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

int main() {
  int n;
  cin >> n;

  vector<int> v(n);

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

  sort(v.begin(), v.end());
  
  int max = 0;
  for (int i = 0; i < n; i++) {
    max += v[i] * (n - i);
  }
  
  cout << max;

  return 0;
}

 

 

 

 

코드 설명

핵심은 sort를 이용하여 입력받는 시간들을 오름차순으로 정렬하는 것이다.

문제에서 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다고 언급하고 있다.

하지만, 글을 자세히 살펴보면 이미 답을 알려주고 있다.

 

뒤쪽을 잘 읽어보면 시간의 합을 1+3+6+9+13 = 32분으로 할 때 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다고 하는데, 작은 시간부터 큰 시간으로 더할 수록 최소합을 구할 수 있기 때문이다.

 

왜냐하면 뒷 사람은 앞의 사람의 시간을 모두 더해야 하기 때문에,

앞에서 적은 시간이 걸릴수록 최소한으로 더할 수 있다.

1
1 3
1 3 6
1 3 6 9 
1 3 6 9 13

 

이러한 구조로 모두 더한 최종 값을 구하게 된다. 

참고로 algorithm 헤더의 sort 함수를 이용하면 간편하게 코드를 작성할 수 있다.

그리디 개념이 들어간 별찍기 문제 느낌..😂

 

 

 

 

---