백준 9576. 책 나눠주기

tose33 2023. 2. 3. 15:16

9576번: 책 나눠주기

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

www.acmicpc.net

그리디 알고리즘.

가장 먼저 생각나는건 a기준 오름차순 정렬, a가 같다면 b 기준 오름차순 정렬이다.

그런데 이렇게 하면 예외가 발생한다.

1 5 // 1

3 10 // 3

3 11 // 4

4 4 // ?

위와 같이 4 4 를 요구한 학생에게 책을 주지 못해 총 3개의 책을 나눠줄수 있다.

b기준 오름차순 정렬, b 같다면 a 기준 오름차순 정렬.

4 4 // 4

1 5 // 1

3 10 // 3

3 11 //5

작은 번호의 책부터 나눠줄 것이기 때문에 b기준 오름차순 정렬 해놓고, 줄수 있는 가장 작은 번호의 책을 차곡차곡 주면 된다.