[백준] 9576번: 책 나눠주기

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

골드 Level1 문제.

n권 중에 최대로 줄 수 있는 책 수를 구하는 건 줄 알았는데 그게 아니라 학생의 수를 구하는 것이라서 틀렸던 문제

처음엔 아쉽이었는데, 두번째 때 해결함!

-틀린풀이: 

다른 사람에게 준 책 수를 books리스트에 넣고, 최종 리스트의 합이 답이라고 생각해서 짠 코드이다

student의 i행의 0열부터 1열까지의 책번호 중에 남아있는 책이 있으면 주는 방식으로 생각했다 

그런데 학생수를 구하는 것이었으므로 틀렸다

 

5번,10번에 n+1, student[i][1]+1로 코드 입력해야한다. 그냥 n,student[i][1]로하면 indexError 발생

 

case =int(input())
for _ in range(case):
    n,m=map(int,input().split())
    student=[]
    
    for _ in range(m):
        student.append(list(map(int,input().split())))
    student=sorted(student,key=lambda x: x[1])
    
    cnt=0
    books=[0]*(n+1) #i번째 책이 아직 있는지 확인하는용
    for i in range(m):
        for j in range(student[i][0],student[i][1]+1):
            if books[j]==0: #아직 안 나눠준 책이라면 준다
                books[j]=1
                cnt+=1
                break
    print(cnt)

-정답풀이: 

cnt 추가하고, student 리스트 1열로 정렬하고, 학생이 처음 책을 받았을 때 cnt세고 break하는 것까지 추가했다 

1열로 정렬하는 이유는 

N, M = 3, 3 이고 각 학생들의 신청숫자가 [ (1,2), (1,3), (2,2) ] 이라고 가정할 때, 첫 번째 학생에게 1번 책, 두 번째 학생에게 3번 책, 세 번째 학생에게 2번 책을 주면 된다.
만약 그냥 정렬을 한다면 첫 번째 학생이 1번 책, 두 번째 학생이 2번 책을 가져가 세 번째 학생은 책을 가져가지 못하게 된다. (출처: https://velog.io/@zwooo96/%EB%B0%B1%EC%A4%80-9576%EB%B2%88-%EC%B1%85-%EB%82%98%EB%88%A0%EC%A3%BC%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython)