[Silver V] 귀찮음-16208

[문제 위치]

https://www.acmicpc.net/problem/16208

[문제 풀이]
이 문제는 그리디를 통해 해결하는 문제이다.
막대의 총 길이를 S라 두고 길이 x를 떼어내면 비용이 x(S-x)이므로, S가 클 때 곱해지는 값이 커져 비용이 증가하니 작은 조각부터 차례로 잘라내는 것이 유리하다.
따라서 막대 길이들을 오름차순으로 정렬하고, 남은 합을 유지하며 각 a[i]에 대해 a[i] * (남은 합 - a[i])를 누적하면 한 번의 정렬 뒤 선형으로 최소 비용을 구할 수 있다.
아래는 이를 구현한 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    long long total = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total += a[i];
    }

    sort(a.begin(), a.end());              // 작은 것부터 자른다
    long long ans = 0;
    long long remain = total;
    for (int i = 0; i < n; ++i) {
        remain -= a[i];                    // 남은 합에서 현재 조각 제거
        ans += a[i] * remain;              // a[i] * (남은 합) 누적
    }
    cout << ans << '\n';
    return 0;
}