[파이썬] 백준 9576 : 책 나눠주기 (골드2)

[파이썬] 백준 9576 : 책 나눠주기 (골드2)

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

---

풀이

방향성 생각

• 구간의 맨 앞 요구부터 책을 나눠준다.
  • 피벗 세팅은 앞이든 뒤든 상관 없다.
  • 피벗이 앞이면 앞부터, 뒤면 뒤부터 세팅
• a<b 이므로 구간이 끝나는 b 위주로 정렬한다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

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

    N,M = map(int,input().split())

    # 입력 받아서, 끝 구간을 기준으로 정렬한다. 피벗을 앞으로 정한거니까 구간이 빨리 끝나는 사람부터 처리하기
    demands = [list(map(int,input().split())) for _ in range(M)]
    demands.sort(key=lambda x: x[1])

    books = [True]*(N+1)
    answer = 0
    for s,e in demands:

        # 처음 찾은 책 위치 idx
        idx = 0
        for i in range(s,e+1):
            if books[i]:
                idx = i
                break

        # 나눠주고 방문처리
        if idx:
            books[idx] = False
            answer += 1
    print(answer)

코멘트

• 이분 매칭인가로도 풀던데 첨 보는거라 패스