[백준 16208번] [그리디] 귀찮음

잘 생각해보면 최대한 큰 숫자들은 나중에 자르는 것이 유리하다.

왜냐하면 남아있는 숫자가 크면 클수록 곱해지는 것이 더 커지기 때문이다.

 

따라서 이 지점에서 정렬을 하고 작은 숫자들부터 choice하는 아이디어를 확보하면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int main(void){
    fastio;
    int n;
    cin >> n;
    vector<int> data_store;
    int current_length = 0;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        data_store.push_back(temp);
        current_length += temp;
    }
    sort(data_store.begin(), data_store.end());

    long long result = 0;

    for(int i = 0; i< n; i++){
        result += data_store[i] * (current_length - data_store[i]);
        current_length -= data_store[i];
    }
    cout << result << "\n";
    return 0;
}