[백준] 11399 ATM (C++ - 그리디 알고리즘)

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

👀 문제 설명

ATM 앞에 N명의 사람이 서있고, i번 사람이 돈을 인출하는데 걸리는 시간은 P(i)분이다. 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하면 된다.

예시 : 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2인 경우

• [1, 2, 3, 4, 5] 순서대로 섰을 때 -> 3 + (3+1) + (3+1+4)+ (3+1+4+3) + (3+1+4+3+2) = 39분이 걸린다.
• 그리디 알고리즘 적용 : [2, 5, 1, 4, 3] 순서대로 섰을 때 -> 1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 32분이 걸린다.

입력 : 사람의 수(N)이 주어지고, 각 사람이 돈을 인출하는데 걸리는 시간 P(i)를 받는다.
출력 : 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

🔨 해결 방법

그리디 알고리즘을 적용하면 된다. 오름차순으로 P를 정렬한 뒤, 각 값을 더해주면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
#define endl "\n"

// title : ATM
// level : silver IV

int main(){
    cin.tie(0); cout.tie(0);

    int N;
    cin >> N;

    int* times = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> times[i];
    }

    sort(times, times+N);
    
    int result = 0;
    for (int j = 0; j < N; j++) {
        result += (N-j) * times[j];
    }
    cout << result;
    return 0;
}