[백준] 2109번 : 순회 강연 - JAVA [자바]

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

---

그리디 알고리즘 문제이다.

1. 강의를 가격순으로 내림차순으로 정렬한다.
2. 날짜 배열을 생성한다.
3. 강의 배열을 탐색하면서 이 강의가 날짜 배열에 들어갈 수 있는지 본다.
4. 있다면 날짜 배열에 대입하고 값을 정답에 더해준다.
5. 없다면 그 전 날짜 즉, 기한이 되기 전인 날짜 배열에 들어갈 수 있는지 1일까지 탐색하며 없다면 패쓰한다.

예를 들어

4
10 4
20 2
30 2
40 1

이러한 예제가 있다고 해보자

먼저 강의 가격순으로 배열이 정렬된다.

40 1
30 2
20 2
10 4

그 후 가격이 큰 순서대로 탐색하며 그 강의의 날짜 기한을 살펴본다.

값이 40인 강의의 기한은 1일이므로 날짜 배열의 1 즉, day[1]을 살펴본다. 비어있으므로 40 강의를 넣고 정답에 더해준다.

그 다음으로 30 인 강의도 day[2]에 넣어주고 가격을 더해준다.

그 다음 20인 강의도 날짜 배열을 살펴본다. day[2]를 살펴보고 그 전날인 day[1] 도 살펴 봤지만 들어갈 공간이 없으므로 저 강의는 진행하지 못한다. 패쓰

마지막으로 10인 강의를 탐색한다. 날짜 배열 day[4]는 비어있으므로 대입하고 정답에 더해준다.

결국엔 답이 80이 된다.

---

public class bj2109 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        lecture[] lectures = new lecture[N];

        int lastDay = -1;
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split1 = line.split(" ");
            lectures[i] = new lecture(Integer.parseInt(split1[0]), Integer.parseInt(split1[1]));
            lastDay = Math.max(lastDay, lectures[i].day);
        }

        // 페이가 쎈 것부터 확인
        Arrays.sort(lectures, (o1, o2) -> o2.pay - o1.pay);

        boolean[] day = new boolean[lastDay + 1];
        long answer = 0;
        for (lecture l : lectures) {
            int d = l.day;
            while (d > 0) {
                if (!day[d]) {
                    answer += l.pay;
                    day[d] = true;
                    break;
                }
                --d;
            }
        }

        System.out.println(answer);
        br.close();
    }

    public static class lecture {
        int pay;
        int day;

        public lecture(int pay, int day) {
            this.pay = pay;
            this.day = day;
        }
    }
}