개발일지

www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 접근 처음에 Disjoint-Set과 LCA를 고민했다. Disjoint-Set을 고민한 이유는 간선을 추가할(샘플을 측정) 때 Disjoint-Set의 Union연산을 통해 하나의 Set으로 만들고, Find연산으로 쉽게 UNKNOWN인지 알 수 있기 때문이다. LCA를 고민한 이유는 무게차이를 구할 때 공통 조상 노드를 찾아서 거리를 구하면 logN만에 쉽게 거리를 찾을 수 있기..