[백준] 책 나눠주기 9576.python

 문제

- 총 N권의 책을 최대 몇 명에게 나눠 줄 수 있는지 찾는 문제

- 학생들은 a에서 b까지 책 번호 내에서 책을 받는다.

 

 해설 및 코드

참고 블로그: steady-coding.tistory.com/230

[BOJ] 백준 9576번 : 책 나눠주기 (JAVA)

- 해당 문제는 그리디로 해결이 가능하다.

- b로 정렬 후 a로 정렬한다.

- 그 이유는 해당 블로그에 잘 나와있다.

# 그리디
T = int(input())

for _ in range(T):
    N, M = map(int,input().split())

    books = []
    for _ in range(M):
        [a, b] = map(int, input().split())
        books.append( [a, b] )

    # b를 기준으로 정렬 후, 같으면 a로 정렬
    books.sort(key = lambda x: (x[1], x[0]))

    # 정렬한 순서대로 a번의 책을 준다.

    nl = [False for i in range(N+1)]

    result = 0

    for book in books:
        for i in range(book[0], book[1]+1):
            if nl[i] == False:
                nl[i] = True
                result += 1
                break

    print(result)

 

 

 

 

Python 문법 정리

- False로 초기화 된 list

nl = [False for i in range(N+1)]