(JAVA) 백준 9576번 : 책 나눠주기

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

9576번: 책 나눠주기

 

 

그리디 알고리즘이다.

 

정답률에 비해 난이도는 죠금 쉬운 편

 

 

처음에 정렬 기준을 b - a 로 잡았으나

50% 이상 가지 못하고 틀렸다는 결과를 받았다.

 

 

a를 기준으로 정렬하면

 

1 3

2 2

1 2

일 경우

 

1 2

1 3

2 2

로 정렬되기 때문에 앞에서 1, 2를 가져가 버리니 정답이 2가 나오게 된다. (실제로는 3이 정답)

 

 

 

그래서 b - a를 기준으로 정렬하고, 같을 경우 a를 기준으로 정렬했지만

오답.

 

그럼 b를 기준으로 오름차순 정렬하고, 만약 b가 같을 때 b-a 를 오름차순으로 정렬하면 어떨까? 생각했다.

 

 

b번째 책 까지만 가져간다는 것을 알면!

 

앞에 1번부터든 2번부터든

남는 책이 있다면 주워가면 되고

없으면 줍지 못하기 때문에!

 

 

 

1) b를 기준으로 오름차순 정렬

2) b가 같을 때 b-a 를 오름차순으로 정렬

 

 

하면 풀 수 있다.

 

 

이 부분 외에는 기초적인 부분이기 때문에

 

소스코드만 남겨두겠다.

 

 

 

감사합니다.

 

소스코드

---

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

// 책 나눠주기
// 그리ㄷㅣ 
public class p9576 {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int tc = Integer.valueOf(st.nextToken());
		StringBuilder sb = new StringBuilder();
		
		while(tc --> 0) {
			st = new StringTokenizer(br.readLine());
			int count = 0;
			int n = Integer.valueOf(st.nextToken());
			int m = Integer.valueOf(st.nextToken());
			boolean[] gived = new boolean[n + 1]; // index : 1 ~ n
			ArrayList<Student> students = new ArrayList<Student>();
			
			for(int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.valueOf(st.nextToken());
				int end = Integer.valueOf(st.nextToken());
				Student s = new Student(start, end);
				students.add(s);
			}
			
			// gap 별 정렬
			Collections.sort(students);
			
			// 책 나눠주기 시작 
			int index = 0;
			int bookCount = n;
			while(index < m && bookCount > 0) {
				Student s = students.get(index);
				for(int i = s.start; i <= s.end; i++) {
					if(!gived[i]) {
						count++;
						gived[i] = true;
						bookCount--;
						break;
					}
				}
				index++;
			}
			sb.append(count).append("\n");
		}
		System.out.println(sb.toString());
	}
}

class Student implements Comparable<Student> {
	int start;
	int end;
	int gap;
	
	Student(int start, int end) {
		this.start = start;
		this.end = end;
		this.gap = end - start + 1;
	}

	@Override
	public int compareTo(Student o) {
		if(this.end < o.end) {
			return -1;
		}
		else if(this.end == o.end) {
			return this.gap < o.gap ? -1 : 1;
		}
		else {
			return 1;
		}
//		if(this.gap < o.gap) {
//			return -1;
//		}
//		else if(this.gap == o.gap) {
//			return this.end < o.end ? -1 : 1;
//		}
//		else {
//			return 1;
//		}
	}
}