9576번: 책 나눠주기
백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의
www.acmicpc.net
문제
백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 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개의 줄에는 각각 정수 $a_i$, $b_i$가 주어진다. (1 ≤ $a_i$ ≤ $b_i$ ≤ N)
출력
각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.
코드
import sys
import heapq
input = sys.stdin.readline
for _ in range(int(input())):
q = []
n, m = map(int, input().split())
remain = [True] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
heapq.heappush(q, (b, a))
cnt = 0
while q:
b, a = heapq.heappop(q)
for i in range(a, b+1):
if remain[i]:
remain[i] = False # 책 나눠줌
cnt += 1
break
print(cnt)
b 오름차순, b가 같다면 a 오름차순으로 정렬하여 앞에서부터 자신이 가져갈 수 있는 책 중 가장 앞 번호의 책을 가져가도록 한다.
처음에는 가장 작은 범위를 가진 사람부터 책을 가져가도록 하려고 했는데 틀렸다. 생각해보니 아래와 같은 반례가 있어서 안됐다
1
5 5
1 2
1 4
2 4
3 4
3 5
최소힙에 (b-a, a, b) 이렇게 넣는 경우 범위가 작은 것부터 정렬되어 아래와 같이 갖고 가게 된다.
1 2 => 1번
3 4 => 3번
2 4 => 2번
3 5 => 4번
1 4 => X
그렇지만 최대한 많은 학생에게 책을 나눠주면 아래와 같이 5명에게 나눠줄 수 있다.
1 2 => 1번
1 4 => 2번
2 4 => 3번
3 4 => 4번
3 5 => 5번
최대한 많은 학생에게 나눠주기 위해서는 최대한 앞번호부터 비는 번호가 없도록 나눠주어야 한다. 이렇게 하기 위해 b 오름차순, 그리고 a 오름차순으로 정렬하여 가져갈 수 있는 책 중 가장 앞번호부터 가져가도록 하였다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 1744번 수 묶기 (1) | 2023.12.23 |
---|---|
[Python/파이썬] 백준 6137번 문자열 생성 (2) | 2023.11.27 |
[Python/파이썬] 백준 1080번 행렬 (0) | 2023.11.13 |
[Python/파이썬] 백준 13164번 행복 유치원 (1) | 2023.10.04 |
[Python/파이썬] 백준 2170번 선 긋기 (0) | 2023.09.28 |