[백준/9576] 책 나눠주기 (Python)

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

9576번: 책 나눠주기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:10:56

 

---

 

문제 설명

 

 

백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 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
2 3
1 2
1 2
1 2

 

출력 예시

 

2

 

 

---

 

풀이

 

그리디로 풀어볼 수 있는 문제. 이런 종류의 라인스위핑 향이 나는 문제는 어느 정도 정형화되어있는 것 같다.

각 책 범위를 우선 (끝점, 시작점) 우선도로 오름차순 정렬하고, 책 범위 리스트를 순차적으로 탐색하도록 한다. 각 책 범위를 시작점에서부터 끝점까지 차례대로 탐색하여, 만약 빈 점이 있다면 빈 점을 방문하여 정답을 1 추가시킨다. 순회 후 정답을 출력하면 풀이 완료.

 

(시작점, 끝점) 우선도로 정렬할 경우, 다음 반례가 발생한다.

1
3 3
1 3
1 1
2 2

 

위 경우는 (시작점, 끝점) 우선도로 정렬할 경우 (1, 1), (1, 3), (2, 2) 순으로 방문하게 되므로, (2, 2)의 경우를 처리하지 못하여 2를 출력한다. 하지만 (끝점, 시작점) 우선도로 정렬할 경우 (1, 1), (2, 2), (1, 3) 순으로 방문하게 되어 모든 경우에 책을 빌려줄 수 있다.

 

비슷하게 범위 기준으로 오름차순 정렬할 경우도 실패한다. 다음 예시를 보자.

 

1
4 4
1 3
1 2
2 3
3 4

 

(1, 2), (2, 3), (3, 4), (1, 3) 순으로 방문하게 되며, 이 경우는 (1, 3)을 처리하지 못하여 3을 출력한다. 하지만  (끝점, 시작점) 우선도로 정렬할 경우 (1, 2), (1, 3), (2, 3), (3, 4) 순으로 4가지 경우 모두 책을 빌려줄 수 있다.

 

 

 

풀이 코드

import sys
input = sys.stdin.readline

def solve() :
  N, M = map(int, input().split())
  book_needs = [list(map(int, input().split())) for _ in range(M)]
  book_needs.sort(key = lambda x : (x[1], x[0]))
  answer = 0
  
  book_visited = [False]*(N+1)
  for a, b in book_needs :
    for i in range(a, b+1) :
      if not book_visited[i] :
        book_visited[i] = True
        answer += 1
        break
  print(answer)

T = int(input())
for _ in range(T) :
  solve()

풀이 완료!

p.s. 이분 매칭 풀이법도 존재한다!