FESTIVAL문제 질문드려요(파이썬3.x)

  • iriya
    iriya

    소스코드

    for i in range(int(input())):
    day,team = map(int,input().split())
    cost = list(map(int,input().split()))
    #최소값
    m = (sum(cost[:team])) / (team*1.0)
    for j in range(day-team+1):
        for k in range(day-team+1-j):
            c = sum(cost[j:team+j+k])/ ((team+k)*1.0)
            if m > c:
                m = c
            if k<day-team-j:
                #현재비용보다 다음 비용이 클 경우 스킵
                if c < cost[team+j+k]:
                    break
    print('%.10f'%m)

    시간제한이 20초던데 100회 기준이니
    회당 적어도 0.2초엔 끊어야 하는걸로 보입니다
    제가 의심가는 부분은 리스트sum 부분외에는
    딱히 시간이 들만한 부분이 보이지 않는데..
    어느 부분에서 지체되어 타임아웃이 나는지 모르겠네요
    파이썬이 처음인지라 도움을 구합니다~


    7년 전
1개의 댓글이 있습니다.
  • seico75
    seico75

    sum 부분이 시간이 오래 걸리는 것이 맞습니다. j, k for 문 안에 sum 이 들어가서 3중 loop 가 되는 것이 문제입니다.
    잘 아시겠지만 sum에서 중복 계산이 많기 때문에 이것을 줄일 필요가 있습니다.

    이 경우 미리 cost 를 accumulate 해놓고 보통 많이 사용합니다.
    acost 가 cost 의 accumulation 된 값이라고 하면.. acost[i] = sum(cost[:i])
    sum(cost[j:k]) = acost[k] - acost[k]
    와 같이 O(1)로 계산이 됩니다.


    7년 전 link

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