반응형
https://www.acmicpc.net/problem/9576
9576번: 책 나눠주기
백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의
www.acmicpc.net
소스코드
풀이
★ 주어진 구간 i,k중 k를 기준으로 정렬하는 이유는 책을 최대한 많은 사람들에게 줘야 하며 범위가 더 크기 때문에 책을 가져갈 수 있는 범위 또한 넓기 때문입니다.
★ 이때 오름차순 정렬을 하는 이유는 예를 들어
ex)
n = 3, m = 3,
[1,2], [1,3], [1,2] 와 같이 책을 가져갈 수 있는 구간이 주어진다면
내림차순 정렬을 하게 될 경우
[1,3]은 1번 책,
[1,2]는 2번 책,
[1,2]는 책 x
=> 총 2권을 책을 나줘줄 수 있습니다.
하지만 오름차순으로 정렬하게 된다면
[1,2]는 1번 책,
[1,2]는 2번 책,
[1,3]은 3번 책
=> 총 3권을 책을 나줘줄 수 있습니다.
★ 나눠줄 책을 확인하는 리스트 check를 만들어, 만약 해당 책을 나눠주지 않았다면(False) True로 바꿔주고, cnt를 1 증가시킵니다. 이 후에 반복문을 바로 빠져나와야합니다. 아니면 두번째 반복문에 해당하는 모든 책을 True로 바꾸게 됩니다 !
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 3111번: 검열 (Python) (1) | 2023.08.14 |
|---|---|
| [백준 알고리즘] 16496번: 큰 수 만들기 (Python) (0) | 2023.08.11 |
| [백준 알고리즘] 17952번: 과제는 끝나지 않아! (Python) (0) | 2023.08.10 |
| [백준 알고리즘] 15903번: 카드 합체 놀이 (Python) (1) | 2023.08.10 |
| [백준 알고리즘] 17413번: 단어 뒤집기 2 (Python) (0) | 2023.08.09 |