보노보노 힌트좀..얻을수 있을까요 ^^;;

  • ibis
    ibis

    안녕하세요 열심히 알고리즘 문제 풀고있는 학생입니다.

    많이 생각해봤지만 계속 TLE가 나와서..ㅠㅠ 염치를 불구하고

    힌트좀 얻어보고 싶어요

    문제 :
    http://algospot.com/judge/problem/read/CAVEMAN

    A.....B.....CD..........이런씩으로 아이들이 있을때
    왼쪽(A)에 닿을 수 있는 불크기가 가장큰 B를 찾아서 그 크기 만큼C를 찾아 지우고요
    C다음에 있는 D에 대해서도 똑같이 불빛이 닿을 수 있는 가장 큰 녀석을 찾는
    씩으로 했습니다.

    근데 20만 해달들이 있을때 다 1의 크기를 갖고 있어버리면
    n^2이..돼서 TLE가 되고 있는거 같습니다.

    좀더 개선할 수 있는 방향이 뭘까요?;;


    6년 전
7개의 댓글이 있습니다.
  • VOCList
    VOCList

    말씀하신 방법이 맞습니다. 현재 불이 닿지 않는 가장 왼쪽에 있는 아이를 기준으로 이 아이를 가장 멀리서 비출 수 있는 등불을 계속 찾아 나가시면 됩니다.

    주어진 데이터를 조금 가공해서 생각해보시면 가장 멀리있는 등불을 찾아가는 시간을 오더 n보다 빠르게 개선 할 수 있는데요. 고민해보세요~


    6년 전 link
  • VOCList
    VOCList

    답은 그래도 안풀리시면 다음에 공개 ㅜㅜ


    6년 전 link
  • Being
    Being

    염치불구하실 건 없습니다! :) 질문이 얼마나 반가운지.. 흑흑..

    VOCList님 말씀대로 전략은 맞는데, 약간 방향을 틀고 자료 구조를 잘 설계하시면 될 것 같습니다.


    6년 전 link
  • ibis
    ibis

    답변 감사드립니다 ㅎㅎ
    조금더 고민해볼께요


    6년 전 link
  • ibis
    ibis

    ㅠㅠ...흑 힌트 조금더 부탁드릴께요...


    6년 전 link
  • ibis
    ibis

    ^^ 해결했습니다~


    6년 전 link
  • VOCList
    VOCList

    ! >_<


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