어제 A번(tju2179) 질문이요.

  • ibroker
    ibroker

    전 당연하게 path cover로 풀어야겠구나 해서 path cover로 풀었는데(문제 특성상 O(n)에 최대 매칭을 찾을 수 있으므로)
    설명이나 소스 코드를 보니깐 다른분들은 더 쉽게 접근하신 것 같네요.
    아무리 봐도 잘 이해가 가질 않아서 그러는데 약간 설명좀 부탁드립니다. ㅠ

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    13년 전
3개의 댓글이 있습니다.
  • zizavino
    zizavino

    죄송합니다 ㅠㅠ
    저 너무 설명을 못하는거 같아요.
    음 저도 path cover를 이용하기 했는데, 다만 인터벌들이 있기 때문에 걍 정렬해놓고 되는대로 붙여나가면 된다고 봐서 그렇게 풀었는데요,,
    "문제 특성상 O(n)..." 이 말씀대로 전 풀었는데(에디토리얼에 있는거가..) 결국 같은 방법으로 한거 같습니다.


    13년 전 link
  • Being
    Being

    저는 이렇게 풀었습니다.
    인터벌들을 그래프로 나타내고 겹치는 걸 엣지를 그으면 결국 거기서 최소 컬러링을 찾는 문제랑 같아지는데요,
    인터벌 그래프에서 최소 컬러링은 그냥 가장 구간이 많이 겹치는 곳이므로
    주어진 구간들 중에 가장 많은 구간이 겹치는 곳을 찾으면 끝입니다.
    그건 뭐 .. 그냐


    13년 전 link
  • ibroker
    ibroker

    답변 감사합니다 ^^


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