[백준] 9576 책 나눠주기 <Java> - 이분매칭, greedy

문제

---

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

 

 

 

풀이

---

우선 이분매칭의 방식으로 풀었다.

이분 매칭 방식은 아래 문제와 같게 풀었다.

https://conpulake.tistory.com/261

[백준] 11375 열혈강호 - 이분매칭

 

시작 책과 끝책의 번호를 저장하고 이를 이용해서 풀었다.

 

<이분매칭 풀이 코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();

	static int n, m;
	static int[] book;
	static student[] students;
	static boolean[] visited;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		
		while(t-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			
			students = new student[n + 1];
			book = new int[m + 1];
			visited = new boolean[m + 1];
			
			for(int i = 1 ; i <= n ; i++) {
				st = new StringTokenizer(br.readLine());
				
				students[i] = new student(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			int answer = 0;
			for(int i = 1 ; i <= n ; i++) {
				Arrays.fill(visited, false);
				if(dfs(i)) answer++;
			}
			
			sb.append(answer + "\n");
		}
		
		System.out.println(sb);
	}
	
	static boolean dfs(int cur) {
		for(int b = students[cur].start ; b <= students[cur].end ; b++) {
			
			if(visited[b]) continue;
			
			visited[b] = true;
			if(book[b] == 0 || dfs(book[b])) {
				book[b] = cur;
				return true;
			}
		}
		
		return false;
	}

	static class student{
		int start, end;
		student(int start, int end){
			this.start = start;
			this.end = end;
		}
	}
}

 

 

이 문제는 이분매칭 외에 그리디 알고리즘을 이용해서 풀 수 있다.

 

회의실 배정 문제와 비슷한 문제로 볼 수 있다.

책의 끝번호 기준으로 정렬을 한다.( 같다면 시작시간이 빠른 순으로 정렬한다.)

 

끝번호 기준으로 하는 이유는,

끝번호가 빠른 학생이 줄 수 있는 책을 먼저 줘도 끝번호가 나중인 학생은 줄 수 있는 책이 남기  때문이다.

시작 번호 기준으로 정렬을 하면 아래와 같은 반례가 발생한다.

3
11
13
22

일 경우 시작순으로 정렬하면 

1 3 인 친구가 2 번 책을 먼저 배정하게 된다. 이렇게 되면 2 2 번 학생이 더이상 배정 할 수 없어 답은 3이지만 2가 나오게 된다.

 

따라서 끝 번호 기준으로 정렬을 해서 문제를 풀고, 시작 부터 끝까지 선택 가능한 책을 선택하고 answer++ 을 해주면 된다.

 

<Greedy 풀이 코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();

	static int n, m;
	static student[] students;
	static boolean[] book;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());
		
		while(t-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			m = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			
			students = new student[n];
			book = new boolean[m + 1];
			
			for(int i = 0 ; i < n ; i++) {
				st = new StringTokenizer(br.readLine());				
				students[i] = new student(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			int answer = 0;
			Arrays.sort(students);
			for(int i = 0 ; i < n ; i++) {				
				for(int b = students[i].start ; b <= students[i].end; b++) {
					if(!book[b]) {
						book[b] = true;
						answer++;
						break;
					}
				}
			}
			
			
			sb.append(answer + "\n");
		}
		
		System.out.println(sb);
	}

	static class student implements Comparable<student>{
		int start, end;
		student(int start, int end){
			this.start = start;
			this.end = end;
		}
		
		@Override
		public int compareTo(student s) {			
			if(this.end == s.end) {
				return this.start - s.start;
			}
			return this.end - s.end;
		}
	}
}