[BOJ] 백준 9576번 책 나눠주기 (Java)

#9576 책 나눠주기

난이도 : 골드 1

유형 : 그리디

9576번: 책 나눠주기

▸ 문제

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

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

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

▸ 입력

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

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

▸ 출력

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

 

문제 풀이  

브루트포스로 모든 케이스를 무작위적으로 경우의 수를 나눠서 조사하기에는 범위가 너무 크기 때문에 그리디 알고리즘으로 풀이할 수 있다. (혹은 이분매칭) 탐욕적인 선택 방식으로는 두 가지를 떠올릴 수 있다.

1. a가 가장 낮은 번호를 고른 학생부터 나눠주기
2. b가 가장 낮은 번호를 고른 학생부터 나눠주기

처음에 1번 방식으로 접근했다가 50% 실패를 받았다. 반례를 찾아보니 (1 3), (1 3), (2 2) 이다. 1번 탐욕 방식으로 하면 (1 3)을 고른 두 학생을 먼저 나눠주게 되므로 (2 2)학생은 받지를 못한다. 최적의 해에 속하지 않는 방식인 것이다. 2번 방식으로 접근하면, b가 가장 낮은 번호인 (2 2)를 먼저 나눠주고, 그 다음 (1 3)을 고른 두 학생에게 나눠주기 때문에 최적 해가 성립하는 것을 알 수 있다.

 

설계

1. (a,b)의 데이터를 리스트 자료구조에 저장한다. list.add(new int[] {a,b});
2. b를 기준으로 오름차순으로 데이터를 정렬한다. Collections.sort(list, ...);
   1. b가 가장 낮은 순부터 a~b에서 아직 빌려주지 않은 가장 번호가 낮은 책을 대여해준다.
3. 총 대여해준 책의 수를 출력한다. total++;

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(tc-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			boolean[] check = new boolean[n+1];
			List<int[]> list = new ArrayList<>();
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());	
				list.add(new int[] {a,b});
			}
			
			Collections.sort(list, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o1[1]-o2[1];
				}
			});
			
			int total=0;
			for(int[] num : list) {
				int start =num[0];
				int end = num[1];
				for(int i=start; i<=end; i++) {
					if(!check[i]) {
						check[i] = true;
						total++;
						break;
					}
				}
			}
			sb.append(total+"\n");
		}
		System.out.println(sb.toString());
	}
}