[BOJ] 포도주 시음 31589번 C++

 

 

문제

산들이는 포도주(와인)를 좋아한다. 그는 마트에서 팔고 있는 N$N$종류의 포도주를 사서 음미하려고 한다. 포도주를 한 병 단위로 사기엔 산들이가 금전적으로 부담이 있기 때문에 그는 작은 용기에 담긴 포도주를 살 것이다. 마트에서 팔고 있는 N$N$종류의 포도주들은 각각 T1$T_1$, T2$T_2$, …, TN$T_N$의 맛을 갖고 있다. 맛의 값이 높은 포도주가 더 맛있는 포도주이다.

산들이가 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 그 맛이 감기약 맛을 방불케 하기 때문에 사실상 0의 맛을 느낀다. 하지만 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 그 두 포도주의 맛 차이만큼 맛을 느낀다. 예외적으로 가장 먼저 마시는 포도주의 맛은 그 포도주 본연의 맛 그대로이다.

산들이는 주량이 매우 적기 때문에 K$K$종류의 포도주를 먹으면 취하여 잠자리에서 뻗어버린다. 따라서 산들이는 N$N$종류의 포도주들 중에서 K$K$종류를 골라 마실 것이다. 산들이는 K$K$종류의 포도주를 마시면서 느낄 수 있는 맛의 합을 극대화하려고 한다.

산들이를 도와 포도주를 얼마나 맛있게 음미할 수 있는지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 포도주의 수 N$N$과 산들이의 주량 K$K$가 주어진다. (1≤K≤N≤300000$1 \le K \le N \le 300\,000$)

두 번째 줄에는 N$N$개의 포도주의 맛 Ti$T_i$가 주어진다. (1≤Ti≤1000000000$1 \le T_i \le 1\,000\,000\,000$)

출력

첫 번째 줄에 산들이가 느끼는 맛의 합의 최댓값을 출력한다.

 

 

접근 방식

 

산들이가 느끼는 맛의 합의 최댓값을 구하기 위해서는

input 이 다음과 같을 때

5 3
8 3 15 8 6

 

15 -> 3 -> 8 을 선택하여 맛의 합이 20 (15 + 0 + 5) 을 만들면 된다

즉, 와인의 맛을 오름차순 혹은 내림차순 정렬한 후,

가장 최댓값, 가장 최솟값 순서대로 선택하여 K개를 채우면 된다!

 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N,K; cin>>N>>K;
    vector<int> v(N);
    for(int i=0; i<N; i++) cin>>v[i];

    sort(v.begin(), v.end());

    int s=0, e=N-2, cnt = 1;
    ll ans = v[N-1];

    while(cnt < K) {
        if(cnt % 2 == 0 ) {
            ans += (v[e] - v[s-1]);
            e--;
        }
        else s++;
        cnt++;
    }
    cout<<ans;

}