[그리디/백준] 9576번: 책 나눠주기

-문제: https://www.acmicpc.net/problem/9576

 

스스로 푼 문제다! 전에 풀었을때는 잘 못해서 아쉬웠는데, 이번에 2트만에 맞혀서 뿌듯하다

학생들이 원하는 책 중 한 권씩만 줄 수 있다고 하고, 또 거기서 최대 학생 수를 구하라고 해서 

정렬을 무조건 해야겠다고 생각했다. 

정렬을 하면, 책을 원하는 순서대로 차곡차곡 주면 줄 수 있는 학생에게 모두 줄 수 있기 때문이다. 

그 다음 count리스트에 1부터 n까지의 인덱스에 1을 넣고, 이게 책이 있다는 의미이므로 학생이 원하는 책 번호 중에 1인 최소 인덱스에 대해 학생수를 카운트(result+=1)하고, 책을 주고(count[j]=0) 그 반복문을 나오면 된다. 

Gold Level2 문제

 

-정답 풀이:

t=int(input())

for _ in range(t):
    n,m=map(int,input().split())
    students=[]
    for _ in range(m):
        students.append(list(map(int,input().split())))
    students.sort()
    students.sort(key=lambda x: x[1])
    result=0
    count=[0]+[1]*n
    
    for i in range(m):
        a,b=students.pop(0)
        for j in range(a,b+1):
            if count[j]==1:
                count[j]=0
                result+=1
                break
                
    print(result)