(백준) 컵라면 - 1781 [java]

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

🐢 설명

제한기간이 있는 문제를 풀어서 최대한 많은 컵라면을 얻어야 되는 문제이다.

 

먼저 우선순위큐를 사용해서 컵라면을 가장 많이 주는 순서로 정렬하고 해당 문제의 마감날을 통해 해당날에 이미 문제를 풀었으면 그 전날 ~ 1일 까지 확인하면서 문제를 풀수 있는날을 찾아주면된다.

 

하지만 단순하게 우선순위큐에서 하나씩 뽑고 날짜 확인하고 이미 차있으면 배열을 돌면서 빈날을 확인하게 하면 시간초과가 나게 된다.

• 총 과제의 개수가 20만개인데 최악의 경우 20만개 * d-day 20만으로 O(N^2)이 된다.

 

Union-Find를 사용하면 이를 O(N)으로 풀수 있다. 어떻게 접근하면 되는지 정리해보자.

 

1. d-day날이 총 과제의 개수 보다 크거나 같다면 전부 풀 수 있으므로 바로 컵라면 개수를 더한다.
2. 아닐 경우
   1. day날 풀수 있다면 바로 그날 푼다. find(day)가 자신의 day와 같다면 풀 수 있음
      • 풀고 나서 하루 전날과 합친다. union(find(전날), 당일)
   2. d-day날 풀수 없다면 ( find(day)가 자신의 day와 다름 ), 하루 전날의 parents인 find(day - 1)과 자신의 day의 parents인 find(day)와 비교한다.
      • 전날의 parent가 자신의 day와 같다면 풀고나서 하루 전날의 parent에 합친다.
      • 만약 그날이 0일 이라면 풀 수 없으므로 넘어간다. (해당 문제는 못품)

자신의 기존 날에 풀수 있으면 풀고, 아니면 parents를 비교해서 O(1)로 이동해서 풀거나 / 0일 이라 못풀거나가 되므로 O(N)으로 풀이가 가능하다.

 

🐢코드

//package Gold이상문제_정리;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N, LastDay;
    static PriorityQueue<Cup> pq = new PriorityQueue<>(Comparator.comparingInt(c -> -c.count));
    static int[] days;

    private static class Cup {
        int deadLine;
        int count;

        public Cup(int deadLine, int count) {
            this.deadLine = deadLine;
            this.count = count;
        }
    }

    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());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int dead = Integer.parseInt(st.nextToken());
            int count = Integer.parseInt(st.nextToken());
            pq.add(new Cup(dead, count));
            LastDay = Math.max(LastDay, dead);
        }

        days = new int[LastDay + 1];
        for (int i = 0; i < LastDay + 1; i++) days[i] = i;

        int answer = solve();
        System.out.println(answer);
    }

    private static int solve() {
        int totalCup = 0;
        int today;
        while (!pq.isEmpty()) {
            Cup now = pq.poll();
            today = now.deadLine;

            if (today >= N) {
                totalCup += now.count;
                continue;
            }

            if (find(today) == today) { // 당일 풀기 가능
                union(find(today - 1), today);
                totalCup += now.count;
            } else if (find(today) != 0) { // 가능한 전일에 미리 풀기 (단, 0일이 아니라면)
                today = find(today);
                union(find(today - 1), today);
                totalCup += now.count;
            }
        }
        return totalCup;
    }

    private static int find(int now) {
        if (days[now] == now) return now;
        return days[now] = find(days[now]);
    }

    private static void union(int left, int right) {
        left = find(left);
        right = find(right);

        days[days[right]] = days[left];
    }
}

🐢 마무리

유니온 파인드를 이용해서 풀수 있는 재밌는 문제였다.