(11399) ATM

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

단계별로 풀어보기

23단계(그리디 알고리즘) 3번째

 

 

 

어떤 두 사람 i, j가 이웃해서 줄을 서 있다고 하자.

이 두 사람이 줄을 서는 순서가 i→j이든 j→j이든 앞사람의 소요 시간에는 영향을 주지 않고, Pi+Pj=Pj+Pi이므로 뒷사람의 소요 시간에도 영향을 주지 않는다.

이때 앞사람까지의 대기 시간을 x라 하면 각 경우에 두 사람의 소요 시간은 다음과 같다.

1) i→j일 때 i의 소요 시간은 x+Pi, j의 소요 시간은 x+Pi+Pj

2) j→i일 때 j의 소요 시간은 x+Pj, j의 소요 시간은 x+Pj+Pi

같은 값은 비교의 의미가 없으니 제외하면 첫번째 경우는 Pi의 소요 시간이 걸리고 두번째 경우는 Pj의 소요 시간이 걸린다.

따라서 P값이 더 작은 사람이 앞에 서는 것이 이득이다.

이를 모든 사람에게 적용하면, P를 오름차순으로 정렬한 대로 줄을 서는 것이 전체 소요 시간을 최소화하는 최적해임을 알 수 있다.

이를 그리디 알고리즘의 Exchange argument 기법이라고 한다. (실제로 증명 과정은 더 복잡하지만, 대충 이런 개념이구나 정도만 이해하고 넘어가면 된다.)

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  sort(v.begin(), v.end());
  
  int ans= 0;
  
  for(int i=1;i<=n;i++){
    v[i]+= v[i-1];
    ans+= v[i];
  }
  
  cout << ans;
  
  return 0;
}