[BOJ 그리디] 순회강연 2109.JAVA

문제 링크 : https://www.acmicpc.net/problem/2109
문제 등급 : 

2109번: 순회강연

문제 해결 프로세스

1. 강연비와 강연 일자 중 강연비를 기준으로 내림차순 하여 정렬한다.
2. 내가 강연할 수 있는 일자를 나열 한다.
3. 가장 강연비가 많은 순서부터 차례대로 강연 일자를 지운다.
4. 강연비를 더하여 최대 강연비를 구한다.

주요 로직

1. Lower Bound를 이용하여 내가 강연할 수 있는 날짜를 하나씩 지워가면서 강연비를 얻어야 한다.
   1. Set을 이용하여 내가 강연할 수 있는 날짜를 나열한다.
   2. 강연비가 가장 많은 강연의 강연 일자를 set.lower(강연일+1)하여 강연할 수 있는 가장 가까운 일자를 찾는다.
   3. set.remove(강연 당일)을 이용하여 강연한 일자는 제거하고 강연비를 더한다.

 

아래와 같이 소스를 공유합니다.

public class 순회강연 {
    public static class Node {
        int d, p;
        Node(int d, int p) {
            this.d = d;
            this.p = p;
        }
    }
    public static int amount = 0;
    public static List<Node> list = new ArrayList<>();
    public static TreeSet<Integer> set = new TreeSet<>();
    public static Comparator<Node> compare = new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return Integer.compare(o2.p, o1.p);
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int maxDeadLine = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int p = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            list.add(new Node(d, p));
            maxDeadLine = Math.max(maxDeadLine, d);
        }

        list.sort(compare);

        for (int i = 0; i <= maxDeadLine; i++) set.add(i+1);
        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            Integer idx = set.lower(node.d+1);
            if(idx != null) {
                set.remove(idx);
                amount += node.p;
            }
        }

        System.out.println(amount);
    }
}