[BOJ] 순회강연 2109.java

 문제

백준의 과제 13904 문제와 같은 문제이다. 점수와 날짜만 서로 바꿔서 입력된다.

해당 문제는 하루에 한 개의 강연만 할 수 있을 때, 가장 최대로 얻을 수 있는 p(강연료)를 구하는 문제이다.

 

 해설 및 코드

package BAEKJOON;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeSet;

public class 순회강연_2109 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] arr = new int[N][2];

		for (int i = 0; i < N; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}

		//높은 강연료 순으로 정렬
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {

				if (o1[0] == o2[0]) {
					return o1[1] - o2[1];
				}

				return o2[0] - o1[0];
			}

		});

		int result = 0;
		
		TreeSet<Integer> set = new TreeSet<>();
		
		for (int i = 1; i < 10001; i++) {
			set.add(i);
		}
		
		
		// O(nlogn)
		for (int j = 0; j < arr.length; j++) {
			
			Integer a = set.lower(arr[j][1]+1);
			
			if(a == null)
				continue;
			
			
			result += arr[j][0];
			set.remove(a);
		}

		System.out.println(result);

	}
	
	
}

해당 문제는 강연료를 기준으로 문제를 해결하면 O(nlogn)에 해결 할 수 있다.

먼저, 강연료를 기준으로 배열을 정렬하면 배열은
(100, 2) ➡ (50, 10) ➡ (20, 1) ➡ (10, 3) ➡ (8, 2) ➡ (5, 20) ➡ (2, 1)
로 정렬이 된다.

이후 정렬된 배열의 순서에 맞춰, 강연이 가능한 날짜(2일이면 1일, 2일 가능)가 존재하면 된다.

해당 날짜는 Lower Bound로 구할 수 있다.

예를 들어, 첫 번째 배열인 2일에 100의 강연료를 받기 위해서는 3의 Lower Bound가 존재하면(1일 또는 2일) 된다.

강연은 최대한 할 수 있는 마지막날에 가까울수록 강연을 할 수 있는 경우가 많아 지므로(그리디) Lower Bound 위치의 날짜를 배열에서 제거해주면 된다.

아래는 위 알고리즘을 그림으로 그린 것이다.

X는 강연을 할 수 있는 날짜이고, 강연을 한 후 배열에서 제거된다.

파란색으로 되어 있는 것은 강연을 하지 못해 얻지 못한 강연료이다.