백준 9576 책 나눠주기

https://www.acmicpc.net/problem/9576

 

요청자의 [a,b] 쌍이 주어졌을 때

b기준으로 쌍을 정렬(오름차순)하거나 a기준으로 쌍을 정렬(내림차순)하는 방식으로

모두 문제의 해결이 가능합니다. 

 

나눠줄 책의 수 N=5, 신청인원 M=5이고

다음과 같은 신청이 있다고 가정해 봅시다.

a b

2 3
3 4
2 5
1 5
3 4

 

* b기준으로 쌍을 정렬하는 경우

 

[a,b]의 범위로 신청했을 경우
[a,b]쌍을 b를 기준으로 오름차순으로 정렬합니다.
[a,b]쌍을 루프를 돌면서 a~b의 범위에서 낮은 번호의 책부터 나눠줍니다.
이 때 나눠준 책은 체크표시를 해 줍니다. (보통 visited[] 배열...)

 

b를 기준으로 정렬하면 아래와 같습니다.

a b

2 3
3 4

3 4
2 5
1 5

 

visited 초기 배열은 숫자 아래와 같습니다.

[0, 0, 0, 0, 0]

 

아래와 같이 요청을 하나하나 처리해 갑니다.

 

a b

2 3   2부터 3까지 순서대로 방문을 하는데 2번 책이 있으므로 나누어 주고 체크 합니다.    [0, 1, 0, 0, 0]
3 4   3부터 4까지 순서대로 방문을 하는데 3번 책이 있으므로 나누어 주고 체크 합니다.    [0, 1, 1, 0, 0]

3 4   3부터 4까지 순서대로 방문을 하는데 3번 책은 없고 4번 책이 있으므로 나누어 주고 체크 합니다.    [0, 1, 1, 1, 0]
2 5   2부터 5까지 순서대로 방문을 하는데 2/3/4번 책은 없고 5번 책이 있으므로 나누어 주고 체크 합니다.    [0, 1, 1, 1, 1]
1 5  1부터 5까지 순서대로 방문을 하는데 1번 책이 있으므로 나누어 주고 체크 합니다.    [1, 1, 1, 1, 1]

 

총 5권의 책을 줄 수 있습니다.

 

 

 

* a기준으로 쌍을 정렬하는 경우 

 

[a,b]의 범위로 신청했을 경우
[a,b]쌍을 a를 기준으로 내림차순으로 정렬합니다.
[a,b]쌍을 루프를 돌면서 b~a의 범위에서 높은 번호의 책부터 나눠줍니다.
이 때 나눠준 책은 체크표시를 해 줍니다.

 

a b

3 4   4부터 3까지 순서대로 방문을 하는데 4번 책이 있으므로 나누어 주고 체크 합니다.    [0, 0, 0, 1, 0]

3 4   4부터 3까지 순서대로 방문을 하는데 4번 책은 없고 3번 책이 있으므로 나누어 주고 체크 합니다.    [0, 0, 1, 1, 0]
2 3   3부터 2까지 순서대로 방문을 하는데 3번 책은 없고 2번 책이 있으므로 나누어 주고 체크 합니다.    [0, 1, 1, 1, 0]

2 5   5부터 2까지 순서대로 방문을 하는데 5번 책이 있으므로 나누어 주고 체크 합니다.    [0, 1, 1, 1, 1]

1 5   5부터 1까지 순서대로 방문을 하는데 5/4/3/2번 책이 없고 1번 책이 있으므로 나누어 주고 체크 합니다.    [1, 1, 1, 1, 1]