[알고리즘] 백준 11399번 "ATM" (C/C++) - Don 임베디드

문제요약:

한 대의 ATM을 N명의 사람이 순서대로 사용하려고 한다.
사람은 1번부터 N번까지 번호가 매겨져 있고,
i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄서는 순서에 따라서,
모든 사람이 돈을 인출하는 데 필요한 시간의 합이 달라지게 된다.

예를 들어, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자.
[P1 P2 P3 P4 P5] 순서로 줄을 선다면,
P1은 3(3)분,
P2는 4(3+1)분,
P3는 8(3+1+4)분,
P4는 11(3+1+4+3)분,
P5는 13(3+1+4+3+2)분이 걸린다.
이렇게 모든 사람이 돈을 인출하는 데 필요한 시간의 합은 39분이 된다.

반면에 [P2 P5 P1 P4 P3] 순서로 줄을 서게 되면,
P2는 1분,
P5는 3(1+2)분,
P1은 6(1+2+3)분,
P4는 9(1+2+3+3)분,
P5는 13(1+2+3+3+4)분이 걸리고,
모든 사람이 돈을 인출하는 데 필요한 시간의 합은 32분이 된다.

줄을 서 있는 사람의 수 N과,
N명이 각각 돈을 인출하는 데 걸리는 시간 Pi가 모두 주어졌을 때,
각 사람이 돈을 인출하는 데 필요한 시간의 합의 최소값을 구하는 프로그램을 작성하라.


제약:

시간 제약 1초, 메모리 256MB
사람수 N (1<= N <= 1000)
i번째 사람의 인출 시간 Pi (1<= Pi <= 1000)

 

예제 1 입력.	예제 1 출력.
5 3 1 4 3 2	32

정답 코드:

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// 각 사람이 인출하는데 걸리는 시간을 저장할 객체.
class Person{
public:
    int nTime;
    Person(int nTime) : nTime(nTime) {}
};
 
// 사람 객체들의 벡터 선언.
vector <Person> v;
 
bool compare(Person A, Person B);    // 벡터 정렬 시 사용할 custom 비교 함수.
int calculateSum(int N);             // 총합 계산 함수.
 
int main()
{
    int N, nTmp, nTime, nResult = 0;
 
    // 총 사람 수 입력.
    cin >> N;
    nTmp = N;
 
    while (nTmp-->0)
    {
        // 각 사람이 걸리는 시간을 입력.
        // 사람 object를 생성하여 vector v에 넣음.
        cin >> nTime;
        v.push_back(Person(nTime));
    }
    // sort objects. 걸리는 시간 오름차순으로 정렬.
    sort(v.begin(), v.end(), compare);    
    // 각 사람이 소요한 시간의 합 계산
    nResult = calculateSum(N);
    // 정답 출력.
    cout << nResult;
 
    return 0;
}
 
bool compare(Person A, Person B)    // 오름차순으로 정렬하기 위한 비교함수.
{
    return (A.nTime < B.nTime);
}
 
int calculateSum(int N)        // 정답 계산을 위한 함수.
{
    int nSum = 0, nMultiply = N;
 
    for (int i = 0; i < N; i++)
    {
        // 처음 사람이 인출한 시간은 N 명이 기다리므로 N을 곱하고,
        // 두번째 사람이 인출한 시간은 N-1명이 기다리므로 N-1을 곱하고,
        // ... N번째 사람이 인출한 시간은 1명이 기다리므로 1을 곱해서 
        // 모든 사람이 기다린 시간의 총합을 구한다.
        nSum += nMultiply * (v.at(i).nTime);
        nMultiply--;
    }
    return nSum;
}

 

원본링크: https://www.acmicpc.net/problem/11399