[C++] 백준 11399 : ATM

백준 11399 : ATM

 

문제 링크:

www.acmicpc.net/problem/11399

11399번: ATM

 

 

문제 내용:

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

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

 

 

Idea:

최소 대기시간을 구하기 위해서는 돈을 인출하는데 필요한 시간이 제일 적은 사람부터 줄을 서야한다.

즉, 인출시간이 제일 적은 사람부터 선택하는 그리디 알고리즘(greedy algorithm)이다.

 

tmp : 각 사람의 대기시간

time : 총 대기 시간

 

 

Code:

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int main() {
    int N;
    scanf("%d", &N);
 
    int* arr = new int[N];
 
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
 
    //정렬
    sort(arr, arr + N);
 
    //대기시간 구하기
    int time = 0, tmp = 0;
    for (int i = 0; i < N; i++) {
        tmp += arr[i];
        time += tmp;
    }
    printf("%d\n", time);
    return 0;
}