[백준] 14527: Paired Up - JAVA

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

 

풀이

소들의 수와 milk output이 주어진다. milk output을 기준으로 정렬했다.

 

투포인터를 이용하여 양쪽에서 가운데를 향해 가면서 소의 수를 감소시키고, 0이되면 다음으로 넘어간다.

 

이때 milk output의 합을 정답에 갱신하면 되는 문제였다.

 

---

 

메모리: 46184KB
시간: 3044ms
언어: Java 11

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] cow = new int[n][2];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            cow[i][0] = Integer.parseInt(st.nextToken());
            cow[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cow, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int left = 0;
        int right = n - 1;
        int answer = 0;
        while (left <= right) {
            int a = cow[left][1];
            int b = cow[right][1];
            answer = Math.max(a + b, answer);

            cow[left][0]--;
            cow[right][0]--;
            if (cow[left][0] == 0) {
                left++;
            }
            if (cow[right][0] == 0) {
                right--;
            }
        }

        System.out.println(answer);
    }

}