(Python/🥇2)백준알고리즘 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)

출력:

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

 

 

풀이:

 

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())
for i in range(N):
    n, m = map(int, sys.stdin.readline().split(" "))

    visited = [False for i in range(n + 1)]
    print(visited)
    lst = deque(sorted([list(map(int, sys.stdin.readline().split(" "))) for _ in range(m)], key=lambda x: x[1]))
    res = 0
    # 책이 있는 동안
    while lst:
        a, b = lst.popleft()
        for i in range(a, b + 1):
            if not visited[i]:
                res += 1
                visited[i] = True
                break
    print(res)

 

그리디 문제였다

하지만 학생들의 리스트를 어떻게 정렬할지가 문제이다.

처음엔 x[1],x[2] 로 a기준 오름차순, b오름차순을 했지만

그렇게되면

1
3 3
1 2
1 3
2 2

 

이 데이터에서 12,13,22 로 

1과, 2 가 이미 True 바뀌어 버려서

2,2 는 줄 수 없게 된다.