[알고리즘] BOJ 9576 책 나눠주기

[BOJ] 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)

---

📍 출력

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

---

📍 풀이

✍ 적용 알고리즘

• Union & Find 알고리즘을 적용하여 문제를 해결하였다.

✍ 문제 풀이

• 제출한 신청서(requests)를 내림차순으로 정렬한다.
• 제출한 모든 신청서의 책번호 a 이상 b 이하 중 b 의 find(b) 값을 기준으로 책을 제공하고 만약 find(b) 의 값이 a 보다 작다면 현재 신청서를 제출한 학생에게는 책을 제공하지 않는다.
• 현재 신청서에 작성된 책 번호 사이의 책이 존재한다면 cnt 의 값을 1 증가시킨다.
• 그 이후 b 의 값을 union(b, b-1) 처리한다.

✍ 코드

from sys import stdin
# Union & Find 
def find(x):
    if x != books[x]:
        books[x] = find(books[x])
    return books[x]
def union(x, y):
    x = find(x)
    y = find(y)
    books[max(x,y)] = min(x,y)

T = int(stdin.readline())
for _ in range(T):
    N, M = map(int,stdin.readline().split())
    requests = []
    for _ in range(M):
        requests.append(tuple(map(int,stdin.readline().split())))
    requests.sort(reverse=True) # 신청서 내림차순으로 정렬
    books = [i for i in range(N+1)] # Union & Find를 위한 배열
    cnt = 0 # 학생 수
    for a, b in requests:
        b = find(b)
        if a > b: continue
        union(b,b-1)
        cnt += 1
    print(cnt)