TPATH 문제

  • coldradio
    coldradio

    TPATH 문제입니다.
    고민고민 했는데 더 좋은 솔루션을 못 찾고 있습니다. 조금의 힌트를 얻을 수 있을까 해서 글을 올려 봅니다.

    질문을 뒤져보니 이분 검색+DFS를 사용한다고 되어 있는데 이분 검색을 어떻게 적용해야할지 모르겠더라구요;;

    제가 사용한 방법은
    1. 입력받은 속도에 대해 이중 루프를 돌아 각각의 (LOW, HIGH) 쌍에 대해
    2. DFS로 길이 있는지를 찾는다.

    그러면 시간 복잡도가 O(N^3M)으로 시간 초과가 됩니다. OTL.
    1번을 어떻게 개선해서 이분 검색으로 만들까요?


    9년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.