[코테] 백준 그리디 9576번 문제

9576번 : 책 나눠주기

문제 링크

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

문제 설명

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

조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.

백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다.

각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)

출력

각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.

문제 풀이

처음에는 오름차순 정렬을 이용하여 제출하였으나 오답이였다. 반례는 아래와 같다.

1

4 4

1 3

1 3

2 2

2 4

→ 정답 : 4 / 오답 : 3

내림차순 정렬을 이용하고, 큰 번호의 책부터 꺼내면서 카운트하니 정답이였다. 다른 사람들 풀이를 보니 이분 매칭을 이용해서 푼 것도 있다.

from heapq import heappush, heappop

# 테스트 케이스 입력
T = int(input())

# 테스트 케이스만큼 반복
for _ in range(T) : 
    
    # 학생 및 책 배열 선언
    count = 0
    students = []
    books = []
    
    # N(책수), M(학생수) 입력
    N, M = map(int, input().split())
    
    # 학생 수 만큼 반복
    for i in range(M) :
        
        # a번부터 b번까지의 수를 입력, 입력하자마자 heapq에 오름차순으로 정렬 저장
        a, b = map(int, input().split())
        heappush(students, (-a, -b))
        
    # heappop을 통해 1개씩 꺼내면서 책번호 배열에 저장, count + 1 올리기
    a, b = heappop(students)
    books.append(-b)
    count += 1
    
    while students :
        a, b = heappop(students)
        
        for i in range(-b, -a-1, -1) :
            if i not in books :
                books.append(i)
                count += 1
                break
    
    print(count)