[C++] 백준 온라인저지 ATM 풀이

ATM이 한 대 밖에 없는 은행에서 N명의 사람들이 차례대로 줄을 서서 돈을 뽑을 때,

모든 사람들이 돈을 뽑는데 걸리는 시간의 최솟값을 구하는 문제

 

---

문제의 조건

 

1. 돈을 뽑으려는 사람들의 수 N, N명의 사람들이 각각 돈을 뽑는데 걸리는 시간을 나타낸 배열이 주어짐

(둘째 줄에 주어지는 것이라 실제로는 반복문 돌리면서 배열에 값 입력받기)

 

2. 사람들이 각각 걸리는 시간은 다 다른데 사람들이 뽑는 순서에 따라 최종적으로 걸리는 시간의 합계가 달라진다. 

 

3. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

 

4. 3번의 조건을 읽어보면 오름차순으로 정렬하고 나서 총 누적 시간을 구하면 된다는 것을 알 수 있다. 

 

---

풀이 과정

 

1. 사람들이 돈을 뽑는데 걸리는 시간이 적은 순서대로 정렬한다. 

algorithm sort 함수 사용

 

2. 사람들이 각자 대기한 시간, 대기한 시간과 본인의 작업 시간을 합친 총 작업시간을 구한다. 

그 다음 정답에는 앞 사람의 총 작업시간에 본인의 총 작업시간을 더한 누적 합계를 구한다. 

 

---

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> people;
    for (int i = 0; N > i; i++)
    {
        int j;
        cin >> j;
        people.emplace_back(j);
    }
    
    sort(people.begin(), people.end());
    
    int answer = 0;
    int waiting = 0; //대기 시간(앞 사람의 총 작업 시간)
    for (int i = 0; N > i; i++)
    {
        int processTime = waiting + people[i]; //총 작업 시간 
        answer += processTime;
        waiting += people[i];
    }
    
    cout << answer;
    
    return 0;
}