(Baekjoon) GreedyAlgorithm - (25) 책 나눠주기

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

9576번: 책 나눠주기

 

 

1. N개의 책이 번호로 매겨져있다.

2. 학생은 a,b 사이의 책중 하나를 책에 준다.

3. 첫재줄 = 테스트케이스

   둘째줄 = N,M 

   셋째줄 ~ + M번째줄  = 학생당 책의 범위

 

위와 같이 범위가 있을때 작은범위부터 해결하는 방식으로 코드를 완성했다.

그리고 당당하게 제출 했는데 틀렸다.

아무리 생각해도 예외 케이스가 없길래 다시 한번 따져보니 다음과 같은 예외케이스가 있었다.

 

내가 푼 방식으로 할경우 위와 같이 범위가 있을때

작은범위 -> 앞쪽부터 채우기 

와 같은방식으로 진행을 하였는데 이렇게 할경우 위와 같은 경우에서 최대 4명에게 책을 줄수 있음에도 3명밖에 주지 않는다.

다시 말해서 작은범위에서 1번책 2번책 3번책을 나눠주고 

그 다음 큰 범위에서 이미 1,2,3번책을 나눠주었기에 나누어 줄수가 없는것이다.

다른방법이 필요했다.

 

그렇게 해서 기존의 코드를 수정하고 그냥 그리디하게 접근하여서

시작번호를 기준으로 정렬하고 그다음은 끝나는 번호를 기준으로 정렬하여서 제출해보았다.

하지만 그렇게 해도 정답이 틀렸다.

왜냐하면 위와같은 상황에서는 1,2,3,4 모두 사용할수있음에도 불구하고

내가 한방식으로 정렬을 할경우 (3,3)은 책을 줄수 없기 때문이다.

 

그렇기 때문에 끝나는 기준점을 기준으로 정렬을 먼저 해보니 정답이 나왔다.

하지만 이것이 왜 그러한지 수학적으로는 이해할수가 없었다. 그냥 그럴듯해보이니까 맞춘거같은 느낌이다.

아마도 시작점이 1번부터 오름차순으로 정렬되고 삽입할때 왼쪽부터 삽입하기 때문이 아닐까 추측해본다.

만약에 1000번부터 내림차순으로 정렬하고 오른쪽부터 삽입을 하였더라면 처음에 시도했던 시작번호를 오름차순으로 정렬한후

끝나는 번호를 오름차순으로 정렬해도 진행이 되지 않았을까 생각해본다.

package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class _9576 {

    public static void main(String args[]) {

        Scanner inputScanner = new Scanner(System.in);
        int TestCase = inputScanner.nextInt();

        for (int Test = 0; Test < TestCase; Test++) {

            boolean beakjoon_had_book[] = new boolean[inputScanner.nextInt() + 1];
            int SeoGangUniversity_Student = inputScanner.nextInt();
            int BookRange_Of_Student[][] = new int[SeoGangUniversity_Student][2];

            for (int man = 0; man < SeoGangUniversity_Student; man++) {
                BookRange_Of_Student[man][0] = inputScanner.nextInt();
                BookRange_Of_Student[man][1] = inputScanner.nextInt();
            }

            Arrays.sort(BookRange_Of_Student, new Comparator<int[]>() {
                public int compare(int[] back, int[] forth) {
                    if (back[1] == forth[1])
                        return back[0] - forth[0];
                    else
                        return back[1] - forth[1];
                }
            });

            int beakjoon_distributing = 0;
            for (int i = 0; i < BookRange_Of_Student.length; i++) {
                for (int j = BookRange_Of_Student[i][0]; j <= BookRange_Of_Student[i][1]; j++) {
                    if (!beakjoon_had_book[j]) {
                        beakjoon_had_book[j] = true;
                        beakjoon_distributing++;
                        break;
                    }
                }
            }

            System.out.println(beakjoon_distributing);
        }

        inputScanner.close();

    }
}

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study