BOJ 8016 - Insulator 링크
(2024.03.05 기준 S5)

문제

A를  $A= \sum_{i=1}^{n} {a_i} + \sum_{i=1}^{n-1} {max(0, a_{i+1}-a_i)}$로 정의할 때, a의 순서를 임의로 바꿔서 가능한 A의 최댓값을 출력

알고리즘

간단한 그리디

풀이

$a$를 오름차순으로 정렬해보자. 그럼 이제 첫 번째로 생각할 수 있는 방법은 정렬된 수열 그대로 $A$를 구해보는 것이다. 그러면 $A= \sum_{i=1}^{n} {a_i} + a_n - a_1$가 나올 것이다. 이게 최댓값일까?

$A$에 $a_{n-1} - a_2$를 더해보자. $A$은 무조건 같거나 증가하게 된다. 느낌이 오지 않는가? 오름차순을 정렬된 $a$에서 $A$의 최댓값을 구하기 위해선 $a_1, a_n, a_2, a_{n-1}, \dots$의 순서로 배치하면 된다. 즉, $A= \sum_{i=1}^{n} {a_i} + \sum_{i=n/2}^{n} {a_i} - \sum_{i=1}^{n/2} {a_i}$가 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);
    int A = 0; for (int i = 0; i < n; i++) A += a[i];
    for (int i = 0; i < n / 2; i++) A += a[n - i - 1] - a[i];

    cout << A;
}

• Python

n, *a = map(int, open(0).read().split())

a.sort()
A = sum(a)
for i in range(n // 2):
    A += a[n - i - 1] - a[i]

print(A)