ispark   2년 전

Union-find로 풀어 보았습니다.

40% 정도 가다가 틀림으로 나옵니다.

아이디어는 선후관계가 주어질 때마다 union을 해주고 앞선 사건에 가중치를 줍니다.

이 가중치의 합을 가지고 요구되는 두 사건의 선후관계를 알수 있지 않을까 해서 입니다.

(교수님을 기다려주지 않는다 문제 응용)

잘못된 아이디어 일까요? 고수님들의 도움 부탁 드립니다.

jwvg0425   2년 전

저는 일단 플로이드로 풀긴 했는데 union-find로도 풀리는지 아닌진 잘 모르겠네요 다른 고수분이 답변해주실 듯

ispark   2년 전

아..Union-find로는 어렵겠네요..

교수님을 기다려주지 않는다와는 다른 케이스 입니다. 교수님은..에서는 1 2 3, 1 3 2 (세번째가 무게) 같이 주어졌을 때 2번과 3번의 무게차이를 알 수 있는 반면에

이 문제에서는 알 수 없습니다. (빠른 방법을 찾았다고 좋아했었는데요 ㅠㅠ)

댓글을 작성하려면 로그인해야 합니다.