백준 9576 책 나눠주기 Java

그리디로 분류되어있는 문제인 책 나눠주기 이다.

그리디 외에도 네트워크 플로우, 이분 매칭, 최대 유량등 다양한 방법으로 풀 수 있는 문제인 것 같다.

 

문제의 내용은

책이 1부터 N까지 있다고 할 때

입력받은 a와 b사이에서 책을 하나씩 줄 수 있을 때

M개의 입력받은 a와 b사이에서 최대 몇명에게 책을 줄 수 있는지를 출력하면 되는 문제이다.

 

어떻게 그리디적으로 풀 수 있을지 고민을 많이 했다.

답은 b순으로 오름차순 정렬하는 것이였다.

 

입력 받은 a와 b를 배열에 넣어두고

b순으로 오름차순 정렬을 하고

for문을 돌며 각각의 조건대로 a부터 b까지 

책이 남아있다면 책을 주면 된다.

 

생각해보면 앞에서부터 책이 남아있는지 찾으면

b만 오름차순으로 정렬해놓으면 학생들에게 책을 최대로 많이 줄 수 있는 것이다.

문제는 이런 생각을 스스로 문제만 보고는 생각해내지 못한다는 점이다.

해법만 알면 정말 쉬운 문제인데, 그리디 문제는 해법을 찾기가 참 쉽지않다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
 
public class Q9576 {
 
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(bf.readLine());
        StringBuilder sb = new StringBuilder();
        while(tc-- > 0) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            
            boolean [] check = new boolean[n+1]; // 책이 있는지 체크할 배열
            Book [] books = new Book[m];
            for(int i=0; i<m; i++) {
                st = new StringTokenizer(bf.readLine());
                books[i] = new Book();
                books[i].a = Integer.parseInt(st.nextToken());
                books[i].b = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(books);
            int ans = 0;
            for(int i=0; i<books.length; i++) {
                for(int j=books[i].a; j<=books[i].b; j++) {
                    if(!check[j]) {
                        check[j] = true;
                        ans++;
                        break;
                    }
                }
            }
            sb.append(ans+"\n");
        }
        System.out.print(sb.toString());
    }
 
} class Book implements Comparable<Book> {
    int a;
    int b;
    
    @Override
    public int compareTo(Book o) {
        int r = this.b - o.b;
        if(r==0) r = this.a - o.a;
        return r;
    }
}