#2209 버스터미널

ㅋㅋㅋㅋㅋㅋ 수많은 try와 함께 결국 맞췄다.

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

솔루션은 의외로(?) 쉽게 나온다. 근데, 내가 좀 바보짓을 해서 TLE가 계속 떴는데....
두 중심지 H1,H2이 있다고 가정을 하면

1. H1끼리 연결된 곳에서 최대거리가 나오는 경우

2. H2끼리 연결된 곳에서 최대거리가 나오는 경우

3. 둘 사이를 가로지르며 최대거리가 나오는 경우 

 

3가지 경우가 있는데, 두 노드를 중심으로 둘중에 노드를 골라서 연결한다고 가정을 하면, bruteforcing시 $O(2^N*N^2)$이된다. 
조금 최적화를 해보면, H1에 A번째 노드를 연결을 해서 노드의 최장거리가 나올때의 경우로 생각을 하면, H1과의 거리가 A보다 긴녀석들을 전부 H2에 연결을 하고, H2에 연결되있는 것들 중에 최장거리를 뽑아오는 식으로 하면, $O(N^4)$에 전부탐색가능하고

 

H1와의  연결 길이를 내림차순으로 sorting을 해주면 $O(N^3logN)$에 가능하다.

 H2와 연결길이중 제일큰값,두번째로 큰 값을 들고있으면서 순회해주면 된다.

 

나는 근데 오름차순을 sorting을 하고, 바보처럼 pq로 제일큰 값,두번째로 큰 값을 들고 오는 풀이를 처음에 짰다  - -...
이렇게 되면 시간복잡도는 동일한데 $O(N^3logN)$만큼 추가로 들어가고, 대충 상수가 무지무지 하게 커진다....

이렇게 해서 TLE맞다가, 2개만 들고 있으면 되는걸 알고 그대로 짰다.

근데 문제 자체가 약간 bruteforcing 최적화 느낌이라 좋은 문제인지는 잘 모르겠다.

나쁜 문제는 아닌거 같은데 사고력보다 프로그래밍에 초점을 둔 애매모호한 느낌.