[백준] 31589 포도주 시음 - 투포인터

문제 링크 : https://www.acmicpc.net/problem/31589

🍊해결방법

• 조합을 통해 K개를 구하게 되면 시초
• 문제의 조건 중 맨 처음 포도주는 온전히 맛으로 인정된다는게 중요!!
• 결국은 젤 큰 값을 먼저 마시면 된다
• 정렬을 활용하자
• 테스트 케이스를 보면
  3 6 8 8 15
  첫번째로 15를 먹고
  두번째로 3을 먹을 때는 값이 작으므로 0
  세번째로 8을 먹으면 차이인 5
  즉 20이 나오게 된다
• 정렬을 활용해서 오른쪽 끝에서 한번 왼쪽끝에서 한번 이런식으로 먹어야 차이가 크므로 투포인터 활용

😀풀이

import java.util.*;
import java.io.*;

public class Main {



    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 포도주를 K만큼 고른다
        // 앞서 고른 포도주보다 값이 작으면 0
        // 앞서 고른 포도주보다 값이 크면 차이만큼 느낌
        // 맨처음 마시는것을 젤 큰 것부터 마시자
        // 정렬이 필요
        // 맨뒤와 맨앞 번갈아가면서 마시면 젤 큰 값

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 정렬을 통하여 구해보자
        Arrays.sort(arr);

        int left = 0;
        int right = N-2;

        long max = arr[N-1];
        int cnt = 1;

        if (K <= 2){
            System.out.println(max);
            return;
        }

        while(left < right){

            // 작은쪽은 맛이 없으므로 0이된다
            cnt++;

            if (cnt == K) break;

            // 큰쪽
            max += (arr[right] - arr[left]);
            cnt++;

            if (cnt == K) break;

            left++;
            right--;

        }


        System.out.println(max);


    }// end main



}