[알고스팟] 록 페스티벌

https://www.algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

풀이

대충 보아하니 무식하게 for문 돌려서 전체 케이스로 풀어도 될거 같은 조건인데 파이썬으로 그렇게 푸니 시간초과가 납니다. 다른사람들 답을 보니 c언어에서는 그냥 무식하게 포문만 돌려도 되던데 말이죠.

 

특정구간의 합을 빠르게 구하기 위한 알고리즘 방법으로는 세그먼트 트리, 그리고 합을 누적해서 배열을 만드는 방법이 있는데, 문제에서는 값의 수정이 없으니 누적합(prefix sum)을 활용하였다

 

 

import sys
C = int(input())
for _ in range(C):
    N,L = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))
    sumArr = [arr[0]]
    answer = 987654321
    for i in range(1,N):
        sumArr.append(sumArr[-1] + arr[i])
    for i in range(N):
        for j in range(i,N):
            w = j-i + 1
            if w < L:
                continue
            temp = (sumArr[j] - sumArr[i] + arr[i]) / w
            answer = temp if temp < answer else answer

    print(answer)