withdrawal 문제 자꾸 시간초과 떨어지는 이유를 모르겠네요ㅠ 도와주세요

  • smg529
    smg529

    widthdrawal 문제를 3일째 풀고 있습니다..
    밤에 잠도 잘 못자고
    일도 손에 안잡혀 너무 힘듭니다..

    로컬에서 돌릴때
    극한으로 험한 input값을 랜덤으로 생성하여 넣고 돌려도
    모두 0.5초안에 끝나는데..

    답안제출만하면
    시간초과라고 뜨는데.. 정말 돌아버릴 것 같다는..

    이거 때문에 밤잠도 잘 못자고 너무 힘드네요..
    이럴 땐 어느부분을 더 확인해봐야할까요...

    $ python inputGenerator.py | python withdrawal4_time.py
    0.3634390651
    [Finished in 0.138s]
    0.2593268980
    [Finished in 0.185s]
    0.4605213449
    [Finished in 0.065s]
    0.3399450118
    [Finished in 0.155s]
    0.5184977578
    [Finished in 0.029s]
    0.2905490098
    [Finished in 0.193s]
    0.3603328239
    [Finished in 0.143s]
    0.0970760234
    [Finished in 0.260s]
    0.1866307761
    [Finished in 0.231s]
    0.4397598771
    [Finished in 0.095s]

    inputGenerator.py 소스

    import random
T = random.randrange(10,11)
print str(T)
for i in range(T):
    n = random.randrange(990,1000)
    k = random.randrange(1,n+1)
    print n, k
    tmpstr = ""
    for i in range(n):
        c = random.randrange(1,20)
        r = random.randrange(1,c+1)
        tmpstr += str(r) + " " + str(c) + " "
    print tmpstr

    7년 전
5개의 댓글이 있습니다.
  • Kureyo
    Kureyo
    1. 더 빠른 알고리즘이 존재합니다.
    2. T제한 50, 시간제한 1000ms는 50개의 답을 1초내에 내야한다는 뜻입니다...

    7년 전 link
  • smg529
    smg529

    아 이게 50개의 입력이 한꺼번에 들어올 경우도 1초안에 처리해야 한다는 것이었나요..ㅠ
    감사합니다. 좀 더 튜닝을 해보겠습니다 ㅠ


    7년 전 link
  • smg529
    smg529

    구글링을 해보면 결정문제로 접근하라는 힌트가 있긴한데..
    각각의 누적등수를 계산해보기 전에 철회할 과목인지 여부를 결정할 수 있는 방법이 있는 지 도무지 모르겠네요. 작은 힌트라도 주시면 큰 도움이 되겠습니다..


    7년 전 link
  • minshogi
    minshogi

    소스가 없어서 어떻게 짜신지 잘 모르겠지만 누적 등수를 계산할 때 그리디한 접근이 가능합니다. 최소등수를 이분탐색하는 결정문제로 접근해보세요


    7년 전 link
  • 박요한
    박요한

    http://book.daum.net/detail/book.do?bookid=BOK00019388517BA
    책 보시고 숙면하시길..


    7년 전 link

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