[BOJ] 12764번: 싸지방에 간 준하

copyrat90·2022년 4월 6일

문제 설명

각 사람마다 PC 사용 시작시간 & 종료시간이 주어지고,
항상 빈 PC 중 $idx$ 가 가장 낮은 PC를 사용할 때,
1. 필요한 PC의 총 개수와 2. 각 PC별 사용 횟수를 구하시요.

접근 방법

1. Naive $O(N^2)$ 풀이

우선 시작하는 시간이 낮은 순으로 입력을 정렬한다.

idx	0	1	2	3	4
A[idx]	(10, 100)	(20, 50)	(30, 120)	(60, 110)	(80, 90)

이제 어떻게 해야 할 지 생각해보자.

일단 각 PC가 몇분까지 점유되는지 현황표pc_usage가 필요할 것이다.
그리고 각 PC별 사용 횟수pc_cnt도 따로 기록해야 한다.

우선, $idx=0$ 번째 사람을 보면, 처음이라 PC가 1대도 없으므로, PC 1대를 늘리고 100분까지 사용한다.

i	0
pc_usage[i]	100
pc_cnt[i]	1

다음으로, $idx=1$ 번째 사람은, 20분부터 사용해야하는데,
$i=0$ 번 PC는 그 시점에서 아직 사용중이므로, PC 1대를 늘리고 50분까지 사용한다.

i	0	1
pc_usage[i]	100	50
pc_cnt[i]	1	1

$idx=2$ 번째 사람, 30분부터 사용, 모든 PC 사용중, PC 1대 늘리고 120분까지 사용.

i	0	1	2
pc_usage[i]	100	50	120
pc_cnt[i]	1	1	1

$idx=3$ 번째 사람의 경우, 60분부터 사용하는데, $i=1$ 번 PC가 50분까지 사용되므로, 이제 그 자리가 비었다.
고로 $i=1$ 번 자리를 110분까지 사용한다.

i	0	1	2
pc_usage[i]	100	110	120
pc_cnt[i]	1	2	1

$idx=4$ 번째 사람, 80분부터 사용, 모든 PC 사용중, PC 1대 늘리고 90분까지 사용.

i	0	1	2	3
pc_usage[i]	100	110	120	90
pc_cnt[i]	1	2	1	1

이제 PC가 4대 필요하다는 것과, 각 pc_cnt[i]를 출력하면 된다.

그런데 이번 시작 시간에 빈 자리를 어떻게 찾아야 할까?

Naive 하게 $i=0..len(pc\_usage)$ 까지 순서대로 선형 탐색하며 종료됐는지 판단하면,
각자 개인 컴퓨터가 필요한 최악의 경우, $O(N)$ 개를 뒤져봐야 한다.
모든 사람을 이렇게 보면 $O(N^2)$ 으로 $N\le100,000$ 에선 시간 초과이다.

2. $O(N \log N)$ 최적화

아이디어

pc_usage 표에서 이번 시작 시간보다 작은 종료 시간을 어떻게 $O(N)$ 안에 찾을까?
선형 탐색으론 안되니, 표에서 종료 시간이 낮은 값부터 보는 게 좋겠다.

가만... 이거 다익스트라 알고리즘 에서의 상황과 비슷하다.
거기선, 표에서 낮은 값을 보려고 최소 힙으로 최솟값을 찾았다.
고로 pc_usage 를 최소 힙으로 선언하면 되겠다.

그런데 이 문제에는 고려할 게 1가지 더 있다.
해당 시점에 사용 가능해진 PC는 여러 대가 있을 수 있는데, 그 중 PC 번호가 제일 작은 PC를 써야 한다.
pc_usage 최소 힙에서 최솟값을 찾았다고 쳐도, 그게 번호까지 가장 작은 PC는 아닐 수 있다.

해법

그래서 내가 해결한 방법은 이렇다.
일단 pc_usage 최소 힙에는 PC의 번호 $i$ 를 포함해 $(end\_time, i)$ 튜플을 저장한다.

$idx$ 번째 사람을 시도할 때, 이제부터 사용 가능한 PC를 전부 pc_usage 최소 힙에서 뺀다. (반복문)
빼면서, 이번에 사용 가능해진 $i$ 번을 available_pc 라는 또 다른 최소 힙에 넣는다.

available_pc.top() 을 꺼내면, 현재 사용 가능한 PC 중 번호가 가장 작은 놈이 나올 것이다.
만일 available_pc 가 비어있다면, 그건 PC를 추가 설치해야 하는 상황이니, PC 늘리는 처리를 하자.

시간 복잡도 분석

입력을 정렬하는 데 $O(N\log N)$ 걸린다.
그리고, 2개의 최소 힙 모두, 최대 $O(N)$ 개까지 원소가 들어갈 수 있다.

pc_usage : $N$ 명 각자 개인 PC가 필요한 최악의 상황이면, 힙에 $N$ 개까지 동시에 존재.
available_pc : $N-1$ 명까지 개인 PC가 필요하고, 남은 $1$ 명이 나머지 모든 사람보다 늦게 이용하는 경우,
사용 가능한 PC $N-1$ 개 중 골라야 하므로 힙에 $N-1$ 개까지 동시에 존재.