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

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 $N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 $10$개의 운동기구가 있을 경우 PT를 $5$번 받으면 모든 기구를 다 사용할 수 있다. $9$개의 운동기구가 있는 경우에도 PT를 $5$번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 $M$을 넘지 않도록 하고 싶다. 이때, $M$의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 $N$이 주어진다. ($1 \leq N \leq 10\ 000$)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 $t_1, t_2, \cdots, t_N$가 주어진다. ($0 \leq t_i \leq 10^{18}$)

출력

 $M$의 최솟값을 출력한다.

예제 입출력

• 예제 입력 1

5
1 2 3 4 5

• 예제 출력 1

5

Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    long long answer = 0;
    cin >> N;
    int left = 0, right = N-1;
    vector<long long> data(N);
    for(int i = 0; i < N; i++) cin >> data[i];
    sort(data.begin(), data.end());
    if(N % 2 == 0){
        while(left <= right){
            long long tmp = data[left] + data[right];
            left++; right--;
            answer = max(answer, tmp); 
        }
    }
    else{
        answer = data[right];
        right--;
        while(left <= right){
            long long tmp = data[left] + data[right];
            left++; right--;
            answer = max(answer, tmp);
        }
    }
    cout << answer << '\n';
}

투 포인터를 활용했다. 투 포인터라고 해서 대단한 지식을 쓴건 아니다. Deque를 쓸 정도로 고급진 문제인지는 모르겠어서.

우선 두 가지 경우가 있다. 짝수인 경우, 그리고 홀수인 경우.

어차피 두 개의 기구를 한번에 쓰게된다면 가장 최소한으로 운동을 조질 수 있는 방법은 총 운동기구 / 2 일 것이다.
그런데 홀수라면 기구가 필연적으로 하나 남는다. 이 경우를 주목해야 한다.

어차피 A와 B라는 두 개의 기구를 쓰게되면 그 두 개의 기구 만큼은 근손실이 일어난다. 근데 이 중에 최댓값을 가진 기구가 섞여있다면 최댓값 + $\alpha$ 를 해야 한다. 즉 겁나 근손실이 생긴다는 것이다. (전국에 있는 헬창 코딩러들 화이팅!)
즉 홀수일때는 일단 단일 기구로써 근손실이 최대로 일어나는 기구를 한번 쓴다 생각해야 한다. 그 이후로는 짝수일때와 똑같다.

우선 오름차순으로 정렬한 후 가장 가벼운것, 무거운것을 하나 하나 까 내려가면서 계산해나가야 한다.