[알고스팟]FESTIVAL

문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.
이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?
예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2}라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이 때 하루 평균 (1+2+3)/3 = 2의 비용이 듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4밖에 되지 않습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N (1 ≤ N ≤ 1000)과 이미 섭외한 공연 팀의 수 L (1 ≤ L ≤ 1000, L ≤ N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다

출력

입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

---

풀이

• 사실 처음에는 연속된 부분수열의 최댓값을 구하는 DP문제와 유사하다고 생각해서 DP로만 고민을 했는데 부분수열의 최소 평균값을 구하는 문제다 보니 도저히 방법이 생각이 나지 않았다

• 비용의 누적합으로 부분합을 구할 수 있다
  -> d[v] - d[u-1]
• L : 최소 행사진행일(섭외된 팀)
• N : 최대 행사진행일
• cost[] : 비용
• dp[] : 누적합

• 최소 행사진행일부터 최대 행사진행일까지의 부분합을 탐색

---

예제

• 입력
  6 3
1 2 3 1 2 3

• i	0	1	2	3	4	5
  cost[i]	1	2	3	1	2	3

• i	0	1	2	3	4	5
  dp[i]	1	3	6	7	9	12

• 만약 3에서 5사이의 부분합이라면 dp[3] - dp[2]를 해주면 될 것이다.

• 이와같은 방법으로 연속된 3개의 수의 부분합 부터 6개의 수의 부분합을
  탐색하며 min값을 찾는다

• 비용은 100보다 크지 않으므로 평균값또한 100이하이고, 초기값은 100으로 설정하여 매번 작은 값이 나올 때마다 answer에 기록한다.

코드

import sys

def prefix_sum(d,u,v):
    if(u == 0):
        return(d[v])
    return(d[v]-d[u-1])


testcase = int(sys.stdin.readline())

for i in range(testcase):
    n,l = map(int,sys.stdin.readline().split())

    cost = list(map(int,sys.stdin.readline().split()))

    dp = [0]*n
    dp[0] = cost[0]

    answer = 100.0
    for i in range(1,n): 
        dp[i] = dp[i-1]+cost[i]
        
    for i in range(l,n+1):
        for j in range(0,n-i+1):
            answer = min(answer,prefix_sum(dp,j,j+i-1)/i)

    print("%0.12f"%answer)