9576. 책 나눠주기

문제 링크

9576. 책 나눠주기

코드

T = int(input())

for test_case in range(T):
    num_list = list(map(int, input().split()))
    book = num_list[0]
    students = num_list[1]

    student_list = []
    book_list = []
    max_total_student = 0
    for books in range(1,book+1):
        book_list.append(books)

    for student in range(students):
        num_list = list(map(int, input().split()))
        #idx = num_list[1] - num_list[0]
        student_list.append(num_list)

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

    for student in student_list:
        min_book = student[0]
        max_book = student[1]

        for i in range(min_book, max_book+1):
            if i in book_list:
                book_list.remove(i)
                max_total_student+=1
                break

    print(max_total_student)

문제 특이사항

• 처음에는 Backtracking 으로 풀어보려고 했다.

• 넣을수 있는 최소 번호부터, 넣을수 있는 최대 번호까지 다 넣어보기 + 안넣는 경우

• 너무 많은 경우의 수가 발생해서 recursion error 발생

• 두번째 방식은 abs 즉 min book과 max book의 크기가 가장 작은 순서대로 정렬해서 넣어보려고 했다.

• 대다수의 케이스가 해결되나 다음과 같은 case에서 오류가 난다.
  1
  4 4
  1 2
  2 3
  3 4
  1 3

• 마지막 방법으로 max book의 순서대로 정렬하고, 넣을때는 min book 부터 넣는 방식으로 했다.