[BOJ] 7578번 : 공장

2013년도 KOI 도대회 고등부 3번 문제이다.

 

간단한 segment tree 문제처럼 보였는데, TLE를 3번 받았다.

 

해법은 간단하다. 1행의 케이블의 번호를 1, 2, 3, 4, 5의 오름차순으로 정렬하고, 2행의 케이블의 번호를 이에 맞게 다시 부여해준다. 그러면 예제의 경우 2, 4, 1, 3, 5가 되는데, 교차는 한 기계에서 그 앞에 자신보다 큰 숫자가 있을 경우에 발생한다. 예제의 경우를 보자. 2의 경우 교차는 0이다. 4의 경우도 교차가 0이고, 1의 경우 앞에 2와 4가 있으므로 교차가 2번 발생하고, 3의 경우는 4로 인해서 한 번, 5는 발생하지 않는다. 따라서 교차횟수는 총 3회이다.

 

따라서 https://jordano-jackson.tistory.com/33에서 다루었던 BOJ 2517번과 같게 segment tree에 query를 처리하고 update하는 방식으로 진행해주면 된다.

 

다만 유의할 점이 몇 가지 있는데, 교차 횟수가 int형의 범위를 넘을 수 있으므로 long long 자료형을 사용하여야 한다.

 

난 이렇게 해서 시간복잡도가 O(NlogN)이 된 것 같은데 자꾸 TLE가 떠서 왜 그런가 살펴봤더니 좌표 재배열에 <map>을 써서 그랬다. 내가 알기로는 <map>의 연산이 O(logN)으로 알고 있었는데 logN을 넘는 경우가 있었나보다.. 어차피 식별번호가 100만 이하로 주어지므로 그냥 array를 써서 O(1)으로 바꾸니 AC를 받았다.

 

전체 time complexity는 O(NlogN)이다.

 

소스는 내 github에서 확인할 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/7578/7578.cpp

GitHub - Jordano-Jackson/PS: Problem solving