[백준] 9576 - 책 나눠주기

1. 문제

9576번: 책 나눠주기

2. 개요

1 ~ N번 까지의 책이 한 권씩 있다. 이를 학생들에게 나눠주려고 한다.

각 학생들은 원하는 책을 a b 형식으로 적어 제출한다. a ~ b 사이의 번호인 책을 원한다는 얘기이다.

이런 방식으로 학생마다 한 권씩 책을 나눠줄 때, 책을 나눠줄 수 있는 최대 학생 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

일단 책의 분배 여부를 알 수 있는 리스트를 만든다.

번호가 작은 책부터 나눠준다고 가정한다.

그렇다면 b가 작은 학생부터 나눠주는것이 가장 바람직한 방법이 된다.

그러므로 학생들이 제출한 내용에서 b를 기준으로 오름차순 정렬한다.

정렬할 때는 a ≤ b이므로, a는 일단 고려할 필요가 없다.

다음으로 정렬된 제출표를 하나씩 탐색하면서 a번째 책부터 b번째 책을 둘러본다.

이 과정에서 아직 분배된 책이 없다면 그 책을 해당 학생에게 나눠주며 분배 처리하고 답을 1늘린 후 다음 학생으로 넘어가는 것을 반복한다.

모든 학생에 대한 작업을 완료했다면 답을 제출하고 다음 테스트케이스로 넘어간다.

3-2. Python

import sys

T = int(sys.stdin.readline())

for t in range(T):
    N, M = map(int, sys.stdin.readline().split())

    answer = 0
    books = [0 for _ in range(N+1)]
    students = []

    for i in range(1, M+1):
        students.append(list(map(int, sys.stdin.readline().split())))

    students.sort(key = lambda x : x[1])

    for s in students:
        for i in range(s[0], s[1]+1):
            if books[i] == 0:
                answer += 1
                books[i] = 1
                break

    print(answer)

3-3. C#

internal class Program
{
    static string[] input;
    static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());

        for (int t = 0; t < T; t++)
        {
            input = Console.ReadLine().Split();

            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            int answer = 0;

            int[] books = new int[N + 1];
            List<int[]> students = new List<int[]>();

            for (int m = 0; m < M; m++)
            {
                input = Console.ReadLine().Split();

                students.Add(new int[] { int.Parse(input[0]), int.Parse(input[1]) });
            }

            students = students.OrderBy(x => x[1]).ToList();

            foreach (int[] student in students)
            {
                for (int i = student[0]; i <= student[1]; i++)
                {
                    if (books[i] == 0)
                    {
                        books[i] = 1;
                        answer++;
                        break;
                    }
                }
            }

            Console.WriteLine(answer);
        }
    }
}