BOJ 13208 - 승현이와 승현이
문제 : https://www.acmicpc.net/problem/13208 전에는 못 풀었는데 드디어 풀었다~ state[a][b] : 조승현13이 a에 있고 조승현16이 b에 있는 상태 를 정점으로 하고 c[a] * c[b]를 정점의 비용으로 가지는 그래프를 생각해보자. 우리가 해야 할 것은 state[a][b]에서 state[b][a]로 가기 위해서 지나가는 정점들의 비용의 최대값을 최소화 하는 것이다. 만약에 문제가 정점의 비용을 최소화하는게 아니라 간선의 비용을 최소화하는 문제였다면 MST를 만들어서 구할 수 있을 것 같았다. 비슷한 아이디어로 정점의 비용이 작은 것부터 큰 것 순으로 보면서 트리를 만들어보기로 했다. 과정은 대략 다음과 같다 1. 정점을 비용순으로 정렬하고 비용이 작은 것 부터 본다. 2. 현재 보고 있는 정점이 u라고 하자 3. u와 인접한 정점들을 본다. 인접한 정점은 v라고 하자. 4. 만약 u와 v가 다른 집합에 속하는데 v의 비용이 u의 비용보다 작거나 같다면 u와 v를 같은 집합으로 합친다. 그리고 간선(u, v)를 따로 저장한다. 위 과정을 반복해서 나오는 간선들을 모으면 트리가 된다. 또한 이 트리상의 경로로만 이동하면 문제에서 요구하는 답을 찾을 수 있다. 직관적으로 이해할 수 있으므로 증명은 생략한다. 이제 문제는 트리에서 두 정점을 연결하는 경로상에 있는 정점의 비용 중 최대값을 찾는 문제로 바뀐다. 이건 LCA 를 이용하면 각 쿼리를 O(lgN)에 처리할 수 있다. 문제를 푸는 총 시간 복잡도는 시간 복잡도는 아마 O(N(N+M)+QlgN)이 될 것 같다. (먼저 맞은 사람들 코드를 보니깐 더 빠른 방법이 있나 보다.) 코드 : http://ideone.com/eBn2sQ