BOJ 11399, ATM

ATM 문제는 순서를 바꿔도 상관 없는 문제입니다.

직관적으로 탐욕법으로 풀 수 있다는 걸 눈치챌 수 있습니다.

하지만, 최적 부분구조가 성립하는지 증명을 해보도록 하겠습니다.

N명의 사람들이 서 있다고 할 때, 

우리가 정답으로 고른 순서가

S1, S2, S3, S4, S5라고 해봅시다.

그리고, S1>S2라고 가정해보겠습니다.

이때 걸리는 총 시간은

S1, S1+S2, S1+S2+S3, S1+S2+S3+S4, S1+S2+S3+S4+S5의 합입니다.

즉, 5*S1 + 4*S2 + 3*S3 + 2*S4 + 1*S5이 됩니다.

하지만, S1 > S2이므로, S1과 S2의 위치를 바꿔서 

5*S2 + 4*S1 + 3*S3 + 2*S4 + 1*S5로 계산하면 우리가 원래 정답으로 고른 순서보다

작은 답을 얻을 수 있습니다. 위 과정을 S(i-1), S(i)에 대해 모두 진행해보게 되면,

우리가 원하는 답은, 입력으로 주어진 p1, p2, ..., pn의 수열을 오름차순으로 정렬 한 다음

(p1부터 pi까지의 합)의 합을 구하면

우리가 원하는 답을 구할 수 있다는 것을

증명할 수 있습니다.

예제 입력 1 

5
3 1 4 3 2

예제 출력 1 

32

1 2 3 3 4

= 5*1 + 4*2 + 3*3 + 2*3 + 1*4

= 5+8+9+6+4 =32

따라서 답은 32,

시간복잡도는 정렬하는데 걸리는 시간 O(nlogn)에, 답을 구하는데 걸리는 시간 O(n)으로

총 O(nlogn)의 시간복잡도로 문제를 해결할 수 있습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int main() {
    vector<LL> v;
    LL n; scanf("%lld", &n);
    for (int i = 0; i < n; i++) { LL temp; scanf("%lld", &temp); v.push_back(temp); }
    sort(v.begin(), v.end());
    LL sum = 0;
    for (int i = 0; i < v.size(); i++) {
        sum += (v.size()-i)*v[i];
    }
    cout << sum;
    return 0;
}