ZEROONE 문제 O(n)인데도 시간 초과 뜨네요;

  • 맥커터
    맥커터

    Python 3 버전으로 문제를 푸는데

    분명히 O(n)의 시간복잡도인데 시간 초과가 뜹니다.
    알고스팟에서 검색해보니 py3으로 시간 초과 안뜨고
    푼걸 보면 방법이 있다는 건데...

    힌트 좀 주실 분 계신가요?


    8년 전
5개의 댓글이 있습니다.
  • 투명드래곤
    투명드래곤

    수열 길이가 백만이고 질문이 십만개니까, 매번 수열을 O(n)으로 스캔하는 방법은 시간 초과가 날 수 밖에 없지요.


    8년 전 link
  • 맥커터
    맥커터

    그러면 이진 탐색으로 찾아야 하는건가요?


    8년 전 link
  • hyunhwan
    hyunhwan

    Hint

    • 특정 구간의 누적합을 구하는 문제라고 생각하는게 좋습니다.
    • 이때 스캔 없이 입력으로 주어진 구간에 대해 누적 합을 O(1)로 처리하는 방법이 있습니다.


    8년 전 link
  • 맥커터
    맥커터

    데이터를 스캔하지도 않고 어떻게 누적합을 구하죠?;;
    구간에서의 합이야 등차수열의 합으로 구한다지만
    일단 데이터를 읽어야(스캔 해야) 이 합과 비교를 할텐데...


    8년 전 link
  • 맥커터
    맥커터

    아아.. 스캔 없이, 라는게
    각각 문제에 대해서였군요.
    답변 감사합니다.


    8년 전 link

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