Garage - IOI 2009

BOJ - 주차장

IOI에 이런 문제가 나온줄 몰랐다.

이런 생각이 든다.

1. 그 당시 알고리즘이 많이 연구 & 알려지지 않았거나 (하지만 IOI 2009엔 Archery가 있는걸...)

2. Problem Setter가 문제 내기 귀찮았거나

3. 정말정말 문제 내기 귀찮았거나

4. 빵점 방지용

...2015 Boxes나 2011 Ricehub보다 훨씬 심하다. 2009 set을 오늘 처음 봤기에 (자랑인지는...) 이런 문제가 있으리라고는 생각 못했다...

해법을 작성하겠다.

O(NM)

배열과 Queue의 관점으로 문제를 접근하면 쉽게 떠올릴 수 있다.

차량이 들어오는 순서는 Queue와 같이 진행된다. 즉, 나중에 온 차가 먼저 주차되는 경우는 없다.

차량이 들어올 때, 주차를 할 수 있다면 번호가 가장 작은 주차공간에 주차를 하게 된다. 결국, 주어지는 입력에서 주어지는 차량들이 주차하는 공간을 결정되어 있으므로 우리는 각각의 차량이 어떤 공간에 주차하는지를 구해주면 된다.

차량이 들어올 때, 주차 공간이 비어있다면 N 번 탐색하여 가장 작은 주차공간을 구해주고, 그 위치에 차량을 주차시킨다.

만약, 공간이 비어있지 않다면 Queue에 차량을 넣는다.

차량이 나갈 때면 그 위치를 다시 비어준다. 이 때, Queue에 차가 존재한다면 나가는 위치에 Queue의 가장 앞 차량을 주차시킨다.

위 방법을 반복하면 M명의 차가 주차할 때 각각 배열을 N 번 탐색한다는 것을 알 수 있다.

주차를 하고 나면 어떤 차량이 어떤 위치에 있다는걸 기록하고, 차량이 나가는 것은 한 번에 할 수 있으므로

전체 시간 복잡도는 O(NM).

O(MlgN)

위 방법에서 주차 공간에 세워져있는 차량은 이미 결정되어 있는데도 남은 위치들 중 가장 작은 번호의 공간을 N 번 탐색하며 찾아야 한다.

이를 Heap으로 관리해주면 O(lgN) 만에 구할 수 있어 시간 복잡도가 O(MlgN)이 된다.