자바 - 백준 2109/ 순회강연

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

골드3

구현 방법

• 하루에 최대 한 강연 + 강연마다 마감일과 강연료가 있음 + 최대 수익이 목표
  • → 작업 스케줄링 문제
  • ⇒ 그리디 알고리즘
• p 값(강연료)가 높은 순, p값이 같은 경우 d값(마감일)이 작은 순으로 정렬하면 답을 구할 수 있습니다.
• 마감일이 같은 경우, 마감일에 가장 가까우면서 일정을 잡을 수 있는 일자로 선정합니다.
  • visited 배열을 이용하여 가능한 일자를 구합니다.

날짜 찾기 최적화

• 기존 방식에서는 visited 배열을 이용해 각 날짜마다 강연이 배정되었는지 확인하고, 빈 날짜를 찾기 위해 매번 O(n)의 선형 탐색을 수행했습니다.
• 이를 개선하기 위해 유니온 파인드의 find() 함수를 이용하기로 했습니다.
  • parent[날짜] = 그 날짜 또는 그 날짜보다 이전 중에서 아직 사용 가능한(빈) 날짜를 저장
  • 만약 가능한 날짜가 0인 경우 불가능한것으로 판단합니다.
  • 이 방식은 각 강연마다 빈 날짜를 거의 O(1)로 찾을 수 있습니다.
  • 예시
    • 강연의 마감일 d부터 시작하여, find(d)를 호출해 사용 가능한 가장 가까운 날짜(슬롯)를 찾습니다.
    • 만약 find(d)가 0을 반환한다면, 이는 마감일 이전에 더 이상 사용할 수 있는 날짜가 없다는 뜻으로, 해당 강연을 배정할 수 없음을 의미합니다.
    • 강연을 배정하면, 사용한 날짜 available에 대해 parent[available]을 find(available - 1)로 업데이트하여, 다음번 호출 시 바로 이전의 빈 날짜를 찾을 수 있도록 합니다.

코드

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

/**
* 백준 2109
* 순회강연
* 골드3
* https://www.acmicpc.net/problem/2109
*/
public class Boj2109 {

    private static class Node implements Comparable<Node> {
        int p;
        int d;

        Node(int p, int d) {
            this.p = p;
            this.d = d;
        }

        @Override
        public int compareTo(Node o) {
            if(p == o.p)
                return Integer.compare(d, o.d);

            return Integer.compare(o.p, p);
        }
    }

    private static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        if(n == 0) {
            System.out.println(0);
            return;
        }

        Node[] nodes = new Node[n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            nodes[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(nodes);

        parent = new int[10001];
        for(int i = 1; i < 10001; i++)
            parent[i] = i;

        int answer = 0;
        for(Node node : nodes) {
            int day = find(node.d);

            if(day > 0) {
                answer += node.p;
                parent[day] = find(day - 1);
            }
        }

        System.out.println(answer);
    }

    public static int find(int x) {
        if(parent[x] == x)
            return x;

        return parent[x] = find(parent[x]);
    }
}