문제

---

제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.

준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 $N$일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다. $N$일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.

준원이는 $N$일간 학식에 총 $X$원 이하를 써야 한다.

여러분이 $N$일간 준원이의 메뉴를 잘 골라서, 고른 메뉴의 맛의 합을 최대화 해주자!

입력

---

첫째 줄에는 두 정수 $N$, $X$가 주어진다.

둘째 줄부터 $N$개의 줄에, 각 날에 먹을 수 있는 5,000원짜리 메뉴의 맛 $A$와 1,000원짜리 메뉴의 맛 $B$가 공백을 사이에 두고 주어진다.

출력

---

준원이가 고른 메뉴들의 맛의 합을 최대화했을 때의 값을 출력하라.

제한

---

• $1 \le N \le 100\,000$ 

•  $1\,000N \le X \le 5\,000N$ 

• $1 \le A \le 10,000$, $1 \le B \le 10,000$ 

예제 입력 1

3 9000
40 10
20 5
30 20

예제 출력 1

65

예제 입력 2

1 1000
30 10

예제 출력 2

10

예제 입력 3

1 5000
10 30

예제 출력 3

30

문제 풀이 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int sumOfTasty = 0;
        int[][] arr = new int[n][2];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());

            // 1000원짜리 맛을 다 합침
            sumOfTasty += arr[i][1];
        }

        // 5000원짜리 맛 내림차순 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });

        // 5000원 맛 < 1000원 맛일 경우 아래로 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] <= o1[1]) {
                    return 1;
                }
                return 0;
            }
        });

        // 5000원짜리 음식을 먹을 수 있는 횟수
        int countDown = (x - 1000 * n) / 4000;

        for(int i = 0; arr[i][0] > arr[i][1] && countDown > 0; i++) {
            sumOfTasty -= arr[i][1];
            sumOfTasty += arr[i][0];

            countDown--;
        }

        System.out.println(sumOfTasty);

    }

}

몇 퍼 가다가 결과는 틀렸습니다..
5000원짜리와 1000원짜리를 정렬하는 기준을 잘못 잡은 것 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class P23559 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        int sumOfTasty = 0;
        int[][] arr = new int[n][2];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());

            // 1000원짜리 맛을 다 합침
            sumOfTasty += arr[i][1];
        }

        // 5000원짜리 맛 내림차순 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int oper1 = o1[1] - o1[0];
                int oper2 = o2[1] - o2[0];

                return oper1 - oper2;
            }
        });

        // 5000원짜리 음식을 먹을 수 있는 횟수
        int countDown = (x - 1000 * n) / 4000;

        for(int i = 0; arr[i][0] > arr[i][1] && countDown > 0; i++) {
            sumOfTasty -= arr[i][1];
            sumOfTasty += arr[i][0];

            countDown--;
        }

        System.out.println(sumOfTasty);

    }

}

정렬 기준을 1000원짜리 맛 - 5000원짜리 맛을 오름차순으로 정렬하도록 했더니 결과는 맞았습니다!

참고

Java 두 개 이상의 정렬 기준