[백준 - 9576번] 책 나눠주기 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디

입력

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

풀이

구하고자 하는 것은 백준이가 책을 줄 수 있는 최대 학생 수다.

최대로 주기 위해서는 특정 책을 다음 번에 책을 얻을 가능성이 가장 낮은 친구에게 줘야 한다.

가능성이 가장 낮다는건 예를 들어 2 4, 2 5가 있을 때 2 4가 더 가능성이 낮다. 그러니까 s가 고정되어 있을 때 e가 작으면 가능성이 낮다고 볼 수 있다.

하지만 이것만으로 풀 수 없다.

N과 M의 범위가 작다는 것에 집중하면 어렵지 않게 풀 수 있다.

먼저, 1 ~ 1000 인덱스를 가진 배열을 선언하고, 각 인덱스의 ArrayList를 대입한다.

그리고 친구의 두 정수 a, b 범위에 속하는 인덱스의 list에 삽입한다.
예를 들어 1번 친구의 두 정수가 1 2면, [1].add(1번 친구), [2].add(1번 친구) 해주면 된다.

N, M이 충분히 작기 때문에 최악의 경우에도 O(10000)이다.

모든 친구를 넣어줬다면,

이제 인덱스 1(책의 번호)부터 N까지 돌면서, 그 책을 list에 있는 친구 중 어떤 친구에게 줄 지 선택하면 된다.

list에 있는 친구 중 당연히 e가 작은 친구를 선택하는 것이 최선의 선택이다.
왜냐하면 다음번에 책을 얻을 확률이 가장 낮기 때문이다.

이렇게 앞 인덱스부터 최선의 선택을 한다면, 답도 자연스럽게 최대 학생 수가 도출된다.

여기서 s를 고려할 필요는 없다. 왜냐하면 이미 지나온 인덱스는 최선의 선택으로 학생에게 책을 줬고, 그렇기 때문에 현재 인덱스에서는 s를 체크할 필요없이 e만 체크해서 선택할 수 있게 된다.

이 과정도 시간 복잡도를 보면 최대 O(10000)이다.

소스 코드

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

class Student {
    int n, e;
    Student(int n , int e) {
        this.n = n;
        this.e = e;
    }
}

public class Main  {
    static int T;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        for(int k=0; k<T; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            ArrayList<Student>[] range = new ArrayList[N + 1];
            boolean[] visited = new boolean[M + 1];
            
            for(int i=1; i<=N; i++) {
                range[i] = new ArrayList<>();
            }
            
            for(int i=1; i<=M; i++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine());
                marking(range, i, Integer.parseInt(st2.nextToken()), Integer.parseInt(st2.nextToken()));
            }
            
            int answer = 0;
            
            for(int i=1; i<=N; i++) {
                if(aloc(range[i], visited)) {
                    answer += 1;
                }
            }
            
            sb.append(answer).append('\n');
        }
        System.out.println(sb.toString().trim());
    }
    
    static void marking(ArrayList<Student>[] range, int n, int s, int e) {
        Student student = new Student(n, e);
        for(int i=s; i<=e; i++) {
            range[i].add(student);
        }
    }
    
    static boolean aloc(ArrayList<Student> list, boolean[] visited ) {
        Student student = new Student(1001, 1001);
        for(int i=0; i<list.size(); i++) {
            if(!visited[list.get(i).n] && student.e > list.get(i).e) {
                student = list.get(i);
            }
        }
        if(student.n == 1001) {
            return false;
        }
        
        visited[student.n] = true;
        return true;
    }
}