[백준][C++] 11399. ATM

11508. ATM

11399번: ATM

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

또 정렬과 그리드가 같이 있는 문제!

 

각 사람이 앞 사람들의 인출 시간을 기다리는 시간을 더하는 값의 총합을 구하는 것이다.

그렇기 때문에 앞 쪽에 있는 사람이 인출 시간이 적을수록 총합의 최솟값이 되는 것이다.

오름차순으로 정렬해야하는 이유를 그려봤다. 열심히.

 

알고리즘 설계

 

1. 인출 시간들이 들어있는 배열을 오름차순으로 정렬한다.
2. 앞 사람들의 인출 시간이 적을 수록 뒷 사람들의 기다리는 시간도 적어지기 때문
3. 반복문을 돌려 사람들의 인출하기까지의 걸린 시간을 모두 구한다.

 

이걸 구상한 코드는...

vector<int> times;
int len, curWait = 0;
long long int waitTime = 0;

cin >> len;

for (int i = 0; i < len; i++)
{
    int input;
    cin >> input;
    times.push_back(input);
}

// 오름차순 정렬
sort(times.begin(), times.end());

for (int i = 0; i < len; i++)
{
    // 각자의 인출 시간을 계속해서 더해준다
    // => 현재 사람이 인출하는데 걸리는 시간 
    curWait += times[i];
    waitTime += curWait;
}

cout << waitTime;

 

 

정렬 + 그리디 문제는 항상 아이디어를 떠올리는 것은 항상 신기하고 재미있다!!