[BOJ][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만큼의 돈을 벌 수 있다.

문제 풀이

이 문제에 접근할 때 배낭탐색처럼 p/d로 비율을 따져 접근하려 했지만 단순히 p, d의 순서대로 정렬하여 접근하면 되는 문제였습니다. 아래의 케이스를 정리하면 표처럼 정리됩니다. 

해당 날짜~1까지 탐색하여 빈 곳이 있을 경우 배열에 체크해주면 해결하실 수 있습니다.

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

강연료	일자
100	2
50	10
20	1
10	3
8	2
5	20
2	1

<풀이과정>

1. (p:100, d:2)

1	2	3	10	20
	100

2. (p:50, d:10)

1	2	3	10	20
	100		50

3. (p:20, d:1)

1	2	3	10	20
20	100		50

4. (p:10, d:3)

1	2	3	10	20
20	100	10	50

5. (p:8, d:2) <- 2~1까지 꽉 차있으므로 X

1	2	3	10	20
20	100	10	50

6. (p:5, d:20)

1	2	3	10	20
20	100	10	50	5

7. (p:2, d:1) <- 2~1까지 꽉 차있으므로 X

1	2	3	10	20
20	100	10	50	5

풀이 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int N;
    static Queue<int[]> queue = new PriorityQueue<>((n1, n2) -> (n1[0] == n2[0] ? n2[1]-n1[1] : n2[0] - n1[0]));
    static boolean[] check = new boolean[10001];

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            queue.add(new int[]{p, d});
        }
    }

    private static void process() throws IOException{
        int ans = 0;

        while(!queue.isEmpty()){
            int[] lecture = queue.poll();
            for(int j=lecture[1]; j>=1; j--){
                if(!check[j]){
                    check[j] = true;
                    ans += lecture[0];
                    break;
                }
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

<출처>

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

2109번: 순회강연