원래 문제 그대로 하고 싶었지만 약관에 문제 유출은 금지라고해서 유사문제로 가져옴.

내가 본 시험 기준으로 이야기 하며 난이도 총평을 하자면 소스코드에 주석을 다 달고 2문제를 맞추니

시험시간 2시간중에 31분이 지나있었음... 하지만 친구한테 듣자하니 둘다 못푼 사람도 꽤 있었다고..


그래서 나왔던 알고리즘 종류의 비슷한 난이도의 다른 문제를 acmicpc.net 에서 가져와서 설명함.


우선 1번으로는 그리디가 나왔음. 저 문제와 동일한 개념인데, 저 문제에서는 각 사람마다 돈을 뽑는 시간이 달라

배치를 어떻게 하느냐에 따라 상대적으로 모든 사람이 기다리는 시간의 값이 달라지는데, 그 때의 최솟값을 구하는 것이 목적.

이것은 운영체제의 스케줄링 문제와도 유사함.


우선 문제에서 유추할 수 있는 힌트는 뒷 사람의 대기시간은 앞 사람의 대기시간을 전부 포함한 뒤 자신의 시간을 기다려야 하므로

앞에서 돈을 뽑는 시간이 짧을수록 뒤에 누적되는 값이 작아지는 것을 알 수 있음. 5명이 있는데 돈을 뽑는데 1분 걸리는 사람이 맨 앞에서 뽑아야


1

1+

1+

1+

1+

이렇게 5명의 누적 시간에 1이 더해지므로. 따라서 문제에서 주어지는 시간을 오름차순으로 정렬하여 누적된 값을 구하면

정답을 구할 수 있음을 확인할 수 있음.


#include<iostream>
#include<algorithm>
using namespace std;
  
int main()
{
    int l[1000],n,d=0,ans=0;
 
    cin>>n;
    for(int i=0;i<n;i++) cin>>l[i];
    sort(l,l+n);
 
    for(int i=0;i<n;i++)
        d+=l[i],ans+=d;
    cout<<ans;
}