백준 2109번: 순회강연

백준 2109번: 순회강연

2109번: 순회강연

 

 

- 정렬과 그리디 알고리즘을 활용하는 문제이다.

 

- 2차원 배열, 정렬, 우선순위 큐를 통해 아래로 같은 방법 같이 문제를 해결할 수 있다.

• 먼저 a[N][2], 2차열 배열을 만든 후에 입력을 받는다.
• a배열을 2번째 element가 오름차순이 되도록 정렬한다.
• 정렬을 마치면 위의 그림과 같이 될 것이다.
• PriorityQueue에 a[i][0]의 값을 계속해서 add() 해 준다. 만약 a[i][1]의 값이 PriorityQueue의 크기보다 작으면 PriorityQueue의 크기가 a[i][1]와 같아질 때까지 remove()을 통해 제일 작은 값들을 삭제한다.
• PriorityQueue에 있는 모든 값들을 더하면 답이 된다.

 

- 예제로

4 // N
5 3
1 2
4 3
4 1

의 데이터를 보자.

- 이 데이터에서는 1, 3, 4번째 강의를 가야지 돈을 최대로 벌 수 있다.

• 위 데이터를 정렬하면 아래와 같이 될 것이다.

• 순서대로 a[i][0]의 값들을 우선순위 큐에 add()하면 된다. 그러면 우선순위 큐에는 1, 4, 4, 5 값들이 저장되어 있을 것이다. a[3][1] 의 값은 3이나 우선순위 큐의 크기는 4이므로 가장 작은 1이 remove된다. 따라서 우선순위 큐에는 4, 4, 5 값이 저장되고 이를 모두 더하면 답이 된다.
• 이처럼 a[i][1]의 값보다 우선순위 큐의 크기가 크다면 서로 값이 같아질 때까지 우선순위 큐에 있는 값을 하나씩 remove하면 최종적으로 벌 수 있는 최댓값이 나오게 된다.

 

	import java.util.*;
	import java.io.*;
	public class boj{
	static int n;
	static int[][] a;
	static int ans = 0;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	a = new int[n][2];
	for (int i = 0; i < n; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 0; j < 2; j++) {
	a[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	Arrays.sort(a, Comparator.comparingInt(o1 -> o1[1]));
	PriorityQueue<Integer> pq = new PriorityQueue<>();
	for (int i = 0; i < n; i++) {
	int day = a[i][1];
	pq.add(a[i][0]);
	while (day < pq.size())
	pq.remove();
	}
	while (!pq.isEmpty())
	ans += pq.poll();
	System.out.println(ans);
	}
	}

view raw BOJ_2109.java hosted with ❤ by GitHub

 

- 이 문제와 유사한 문제로는 백준 1781번: 컵라면 문제가 있다. 굉장히 유사한 문제이니 이러한 종류의 문제풀이를 연습하고 있었다면 위 문제도 꼭 풀어보면 좋을 것이라 생각한다.

1781번: 순회공연