[백준, BOJ 2109] 순회강연 (java)

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

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값이 주어진다.

출력

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

728x90

 

예제 입력 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.InputStreamReader;
import java.util.Arrays;
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;
		
		// 입력
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][2];
		int lastDay = 0; // 마지막 마감일
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][0] = Integer.parseInt(st.nextToken());
			lastDay = Math.max(lastDay, arr[i][0]);
		}
		
		int[] pay = new int[lastDay + 1]; // 인덱스에 해당하는 날에 벌 수 있는 최대 수익
		for (int i = 0; i < n; i++) { // 대학에서 제시한 값을 모두 검사
			for (int j = arr[i][0]; j > 0; j--) { // 마감일부터 첫째날까지 보며
				if(pay[j] < arr[i][1]) { // j날 최대 수익보다 현재 검사 중인 대학에서 제시한 값이 더 크면
					int tmp = pay[j]; // j날에 현재 검사 중인 대학에서 제시한 값을 넣어주고
					pay[j] = arr[i][1];
					int k = j - 1;
					// 1 ~ j-1일을 검사해주며 k날 강연을 대신 tmp 강연을 하는 것이 더 큰 수익을 얻을 수 있으면 tmp 강연을 해준다.
					while(k > 0) {
						if(pay[k] < tmp){
							int t = pay[k];
							pay[k] = tmp;
							tmp = t;
						}
						k--;
					}
					break;
				}
			}
		}
		
		int result = 0;
		for (int i = 1; i <= lastDay; i++) {
			result += pay[i];
		}
		
		System.out.println(result);
	}

}