[알고리즘] 백준 2109 순회강연 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 골드4
링크 : https://www.acmicpc.net/problem/2109

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 2만 > Scanner
O(n^2) 풀이 (정렬, 2중 for문): 시간제한 ok
자료형 : 최대 1억 > int사용

풀이

그리디 알고리즘을 많이 풀어본건 아니지만, 어느정도 문제 감은 익힌것 같다. 내일부터는 Dynamic Programming 을 연습해봐야겠다.

처음에는 정렬을 잘못하여 WA (Wrong Answer)가 나왔다. 정렬 이후 알고리즘이 잘못됐나 생각해봤는데, 전혀 틀릴 곳이 없어 곰곰히 생각해보다가, 정렬을 잘못했음을 깨우쳤다.

초반에는 d(d일안에 와서 강연)를 내림차순, d가 같으면 p (강연료)를 내림차순으로 정렬하여 문제를 풀었는데, 처음부터 p(강연료)만 내림차순으로 정렬하면 된다는 사실을 깨달았다.

또한, 입력 데이터는 Scanner로 받았는데, 처음에 568ms가 나왔다. 1등이 292ms인거에 비해서 너무 느렸는데, BufferedReader로 바꾸니까 320ms로 줄어들었다 (?) 그래서 풀이는 BufferedReader로 작성하도록 한다.

알고리즘

1. max[10001] 배열을 만든다.
   max[i] : i일에 강연할 때 받을 수 있는 최대 금액
2. 입력을 받는다.
3. p(강연료) 기준으로 내림차순 정렬한다.
4. 배열을 순차적으로 돌며, for d -> 0 까지 감소시키며 max[d]와 비교하여 d가 더 클경우 최댓값으로 갱신하고 for문 종료.

4번의 경우, 예를 들어

3
10 3
30 3
20 3

인 경우, 1일차에 30, 2일차에 20, 3일차에 10원을 벌어야 하므로 for d -> 0을 사용.

4
10 3
40 2
30 3
20 3

인 경우, p를 기준으로 내림차순 정렬하면

40 2
30 3
20 3
10 3

이 되고,
위 그림과 같이 표현할 수 있다. 3회차에서 20은 원래 max[3]에 들어가야 하지만, 기존 30이 더 높으므로 max[2]와 비교, 그러나 max[2]가 더 크므로 max[1]에 삽입한다.

4회차에서 10은 들어갈 곳이 없다. (max[0]은 사용 안함, max[i]가 i일차까지 강연해주면 받는 돈인데, 1 <= d <= 10,000이기 때문)

코드

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//1. max[10001] 배열을 만든다.
		int[] max = new int[10001];
		
		//2. 입력을 받는다.
		int n = stoi(br.readLine());
		int sum = 0;
		int[][] arr = new int[n][2];
		for(int i = 0; i < n; i++) {
			String[] input = br.readLine().split(" ");
			arr[i][0] = stoi(input[0]);
			arr[i][1] = stoi(input[1]);		
		}
		
		//3. p(강연료) 기준으로 내림차순 정렬한다.
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o2[0] - o1[0];
			}
		});
		
		//4. 배열을 순차적으로 돌며,
		// for d -> 0 까지 감소시키며 max[d]와 비교하여 d가 더 클경우 최댓값으로 갱신하고 for문 종료.
		for(int i = 0; i < n; i++) {
			int cost = arr[i][0];
			int dueDate = arr[i][1];
			for(int j = dueDate; j >= 1; j--) {
				if(max[j] < cost) {
					max[j] = cost;
					break;
				}
			}
		}
		for(int i = 0; i < 10001; i++) 
			sum += max[i];
		
		System.out.println(sum);
	}
	public static int stoi(String str) {return Integer.parseInt(str);}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.