[C++] 백준 BOJ 11399 ATM

문제 링크 : https://boj.kr/11399

A B C D 의 순서로 필요한 시간이 있다고 가정해보자

1 - A

2 - A + B

3 - A + B + C

4 - A + B + C + D

TOTAL - 4*A + 3*B + 2*C + 1*D 로 식이 나오게 된다. 가장 큰 수를 적게 곱하고 작은 수를 많이 곱하는게 이득이 된다.

결국 모든 숫자를 오름차순으로 정렬해줘서 작은 숫자 부터 N - i 번씩 곱해나가는 방식으로 풀면 쉽게 풀린다.

// BOJ 11399 ATM
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int N, sum = 0;
    cin >> N;
    vector<int> time(N);
    for (int i = 0; i < N; i++)
        cin >> time[i];
 
    sort(time.begin(), time.end());
 
    for (int i = 0; i < N; i++) {
        sum += time[i] * (N - i);
    }
    cout << sum;
 
    return 0;
}