[파이썬 | 알고리즘 문제해결전략 | 알고스팟] 록 페스티벌

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

algospot.com :: 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 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

 

풀이

시간이 2초 주어지는데, 테스트 케이스의 경우 N * L = 1000000 이므로, O(n^2)의 형태로 문제를 해결 가능하다.

 

문제를 풀어가는 기본 알고리즘을 설명하자면,

 

최소 L개의 날짜를 선택하고 최대 N개의 날짜까지 선택이 가능하다 즉 [L, N+1) 의 범위를 가지고,

 

또한 날짜의 index는 1일차 부터 N일 차까지 즉, [1, N+1)이 가능하다.

 

따라서 처음 for문은 날짜 index를 1일 부터 순회하고

아래 for문은 몇개의 날짜를 선택할것인가에 대한 순회를 하고,

 

그 내부에서 합 및 평균을 구하면 된다.

 

처음 문제 해결을 함에 있어서, Python 내장함수인 sum을 사용했다. 이러면 2중 for문 안에 sum이 있어서 n^3의 시간복잡도를 가지므로 문제 해결이 불가능하다.

 

따라서 sum에 대해서 더 간단한 접근법이 필요하다.

 

con 리스트에 저장된 비용을, 새로운 sumarr 리스트에 누적합을 넣어줌으로써 해결 할 수 있다.

 

따라서 i번째 날짜부터 j번째 날짜 까지의 합을 구하려던 코드가

 

sum(con[i:j+1]) 에서, sumarr[j] - sumarr[i-1]로 시간복잡도를 줄일 수 있다.

 

최종 코드는 다음과 같다.

 

 

import sys
read = sys.stdin.readline
 
C = int(read())
 
def solve():
    N, L = map(int, read().split())
    con = [0] + list(map(int, read().split()))
    sumarr = []
    sumarr.append(0)
    for i in range(1, N+1):
        sumarr.append(sumarr[i-1] + con[i]) 
    minval = 999999
    for i in range(1, N+1):
        for j in range(L, N+1):
            start, end = i, i+j-1
            if end <= N:
                temp = (sumarr[end] - sumarr[start-1]) / j
                if minval > temp:
                    minval = temp
    print(minval)
 
while C:
    solve()
    C -= 1