[백준] 9576번: 책 나눠주기(그리디)

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

9576번: 책 나눠주기

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(bf.readLine());
		StringTokenizer st;
		for(int tc=0; tc<t; tc++) {
			st = new StringTokenizer(bf.readLine());
			int N = Integer.parseInt(st.nextToken());	// 책 수량
			int M = Integer.parseInt(st.nextToken());	// 나눠줄 학생 수
			boolean[] checkBook = new boolean[N+1];		// 책 나눠줬는지 체크
			int[][] arr = new int[M][2];	// a, b 원하는 학생이 책
			int count = 0;	// 책을 줄 수 있는 최대 학생수
			
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(bf.readLine());
				arr[i][0] = Integer.parseInt(st.nextToken());
				arr[i][1] = Integer.parseInt(st.nextToken());
			}
			
			// b 기준으로 오름차순
			Arrays.sort(arr, new Comparator<int[] >() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return Integer.compare(o1[1], o2[1]);
				}
			});
			
			// 정렬된 기준으로 책 빌려주기.
			for(int i=0; i<M; i++) {
				// a(arr[i][0]) ~ b(arr[i][1])까지 검색
				for(int j=arr[i][0]; j<=arr[i][1]; j++) {
					// 책을 대여해줄  수 있는 상태이면 빌려주고 체크한다.
					if(!checkBook[j]) {
						count ++;
						checkBook[j] = true;
						break;
					}
				}
			}
			System.out.println(count);
		}
		bf.close();
	}

}

풀이

그리디 알고리즘으로 분류되어 있어서 문제를 보고 풀어보려고 헀는데 이분매칭, 네트워크 플로우? 등 다른 알고리즘도 있어서 난이도가 높게 책정되어있는 것 같았다.

문제가 2차원 배열에 학생에게 나눠줄 수 있는 책의 최대 갯수, 뭔가 딱 그리디 + 정렬로 풀릴 것 같아서 정렬을 어떻게 해야할지 고민했다.

a이상 b이하인 책 중 남아있는 책 한권을 골라 학생에게 나누어준다.

그럼 a를 기준으로 정렬할지, b를 기준으로 정렬할지, 오름차순 내림차순 정렬할지를 생각해보았다.

a를 기준으로 정렬한다면 책을 최대로 나눠줄 수 없는데, 다음과 같은 반례가 있다.

 

a b= 1 5

a b= 2 2

a b= 1 5

위의 수를 a를 기준으로 정렬하면

1 5

1 5 

2 2

다음과 같이 되고, 순서대로 한권씩 나눠준다고 하면 각각 1, 2 책을 나눠주고, 마지막 학생에게는 책을 나눠줄 수 없다.

하지만 마지막  학생에게 2, 첫번째 두번째 학생에게 1, 3 을나눠주면 책을 전부 나눠줄 수가 있다.

 

따라서 b를 기준으로 정렬해야겠다는 생각을 했다.

위의 수를 b를 기준으로 정렬하면

2 2

1 5

1 5

와 같이 되고, 반례가 존재하지 않고 책을 최대로 나눠줄 수 있다.