[Java] 백준 2109번 : 순회강연

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

예제 입력 1

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력 1

185

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N;
	private static Class []classes;
	private static boolean []check=new boolean[10001];
	
	static class Class implements Comparable<Class> {	// 강연료와 날짜 정보를 클래스로 관리하며, 강연료 기준 내림차순 정렬되도록 함
		int p, d;

		public Class(int p, int d) {
			super();
			this.p = p;
			this.d = d;
		}

		@Override
		public String toString() {
			return "Class [p=" + p + ", d=" + d + "]";
		}

		@Override
		public int compareTo(Class o) {
			return Integer.compare(o.p, this.p);
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		classes=new Class[N];
		
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			int p=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			classes[i]=new Class(p, d);
		}
		Arrays.sort(classes);	// 강연료 기준 내림차순 정렬
		
		int money=0;	// 학자가 번 강연료
		int idx=1;	// check 배열에서 false인 값의 최소 인덱스
		for(int i=0;i<N;i++) {
			int d=classes[i].d;
			if(!check[d]) {	// 아직 강연하지 않은 날짜이면, 강연을 하고 강연료를 받음
				money+=classes[i].p;
				check[d]=true;
				if(d==idx) idx++;
				continue;
			}
			while(check[d] && d>=idx) {	// 이미 강연한 경우, 강연 가능한 이전 날짜가 있는지 확인
				d--;
			}
			if(d>=idx) {	// 강연 가능한 이전 날짜가 존재하면, 강연을 하고 강연료를 받음
				money+=classes[i].p;
				check[d]=true;
				if(d==idx) idx++;
			}
		}
		
		System.out.println(money);
	}

}

1. 강연 정보를 강연료 기준 내림차순으로 정렬합니다.

2. 반복문을 돌며 해당 강연의 마지막 강연 가능 날짜에 강연이 가능한지 확인합니다.

    2-1. 가능한 경우, 강연료를 받고 해당 날짜 강연 여부를 true로 변경합니다.

    2-2. 불가능한 경우, 이전 날짜 중 강연 가능한 날짜를 찾습니다.

        2-2-1. 가능한 경우, 강연료를 받고 해당 날짜 강연 여부를 true로 변경합니다.

        2-2-2. 불가능한 경우, 다음으로 넘어갑니다.

3. 최종적으로 받은 강연료를 출력합니다.