[Java] 백준 28087 고인물의 졸업 계획 (G4)

문제를 읽는데 상당히 찔렸다.

 

주어진 과목을 조합해서 N~2N사이의 학점을 맞추면 되는 문제이다.

문제 해결 전략

가장 먼저 생각한 것은 그리디 알고리즘이였다. 하나씩 더해보면서 N~2N 사이의 학점의 합을 만들어내면 바로 조그 조합을 출력하도록 하였다.

문제를 푸는 알고리즘은 다음과 같다.

1.    강의를 점수가 높은 순서대로 정렬한다.
2.    높은 점수부터 하나씩 선택하며 합계를 관리한다.
3.    만약 sum + 현재 강의 점수가 require 이상이면서 require * 2 이하라면 선택 후 종료한다.
4.    그렇지 않다면, require * 2를 넘지 않는 한 계속 강의를 선택한다.
5.    선택한 강의의 개수와 번호를 출력한다.

reverse order로 정렬한 이유는 만약 오름차순으로 정렬했을 때 예외가 생기기 때문이다.

만약 1,2,3,4,7,8,9 학점을 갖는 수업들이 있다고 했을 때, 12~15 사이의 sum을 만드는 원소들을 도출한다고 하자. 이 상황에서 순차 탐색을 한다면 1+2+3+4 < 12, 1+2+3+4+7>15가 되어서 제대로 된 탐색을 할 수 없다.

그러나, 만약 reverse order로 정렬한다면 8+7 ≤ 15라는 조합을 만들 수 있게 된다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_28087 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long require = Long.parseLong(st.nextToken());
        long maxSum = require * 2;

        int n = Integer.parseInt(st.nextToken());
        Lecture[] lec = new Lecture[n];
        for (int i = 0; i < n; i++) {
            lec[i] = new Lecture(i + 1, Integer.parseInt(br.readLine()));
        }

        Arrays.sort(lec, (i1, i2) -> Integer.compare(i2.point, i1.point));
        List<Integer> store = new ArrayList<>();

        long sum = 0L;
        for (int i = 0; i < n; i++) {
            int cur = lec[i].point;

            if (sum + cur >= require && sum + cur <= maxSum) {
                store.add(lec[i].idx);
                break;
            }
            if (sum + cur <= require * 2) {
                sum += cur;
                store.add(lec[i].idx);
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(store.size()).append("\n");
        for (int i : store) {
            sb.append(i).append("\n");
        }
        System.out.println(sb);
    }

    static class Lecture {
        int point;
        int idx;

        public Lecture(int idx, int point) {
            this.idx = idx;
            this.point = point;
        }
    }
}

느낀점

가능한 모든 조합 중 하나를 출력하면 되는 문제여서 난이도가 그리 높지 않은 것 같다. 여기서 문제의 난이도를 높이는 방법은 이를 만족하는 최소 수업의 조합을 구하도록 시키는 것 이라고 생각했다. 그래도 문제를 푸는 방식은 비슷할 것이다.

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