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

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

9576번: 책 나눠주기

🔶 풀이

그리드 알고리즘으로 충분히 해결할 수 있는 문제.

 

 

1번부터 N번까지의 책을 가지고 있고, a부터 b까지 중 하나의 책을 최대한 많은 학생에게 나눠주면 된다.

중복된 책을 나눠주면 안되기 때문에 book 배열로 나눠줌 여부를 판단해줬다.

 

문제를 잘 살펴보면 한 가지 예외가 있다.

1
5 4
1 5 // 1번 책을 나눔
2 5 // 2번 책을 나눔
3 4 // 3번 책을 나눔
3 3

 

위의 예제를 순서대로 진행한다면 3명의 학생에게 책을 나눠줄 수 있다. 하지만 정답은 4명이다.

즉, 정렬이 필요하다.

 

b를 기준으로 정렬해주면 예외를 쉽게 해결할 수 있다.

1
5 4
3 3 // 3번 책을 나눔
3 4 // 4번 책을 나눔
1 7 // 1번 책을 나눔
2 7 // 2번 책을 나눔

 

<최종코드>

 

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static class Student implements Comparable<Student>{
        int s, e;
		
        public Student (int s, int e) {
            this.s = s;
            this.e = e;
        }
		
        public int compareTo(Student o) {
            return this.e - o.e;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스
		
        for (int i=0; i<T; i++) {
            st = new StringTokenizer(br.readLine());
			
            int N = Integer.parseInt(st.nextToken()); // 책 개수 (0-N-1번)
            int M = Integer.parseInt(st.nextToken()); // 학부생 수
			
            Student[] student = new Student[M]; 
            boolean[] book = new boolean[N+1];  // 책 나눠줌 여부
			
            for (int j=0; j<M; j++) {
                st = new StringTokenizer(br.readLine());
				
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
				
                student[j] = new Student(S, E);
            }
			
            // 마지막으로 필요한 책을 기준으로 오름차순 정렬
            Arrays.sort(student);
			
            int ans = 0;
            for (int j=0; j<M; j++) {
                Student now = student[j];
				
                for (int k=now.s; k<=now.e; k++) {
                    if (!book[k]) {
                        book[k] = true;
                        ans++;
                        break;
                    }
                }
            }
			
            System.out.println(ans);
        }
    }
}