[AlgoSpot][Python] 록 페스티벌

📒 문제 설명

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

---

✏️ 풀이 과정

📝 1차 시도

• 이 문제에서는 가능한 모든 부분 배열에 대한 평균을 계산하고, 그 중에서 최솟값을 찾는다. (완전 탐색)

• 1차 시도는 Python 내장 함수인 sum을 사용하여 간단하게 구현해보았다.

✨ 소스 코드

import sys

def calculate_min_average_cost(N, L, costs):
    averages = []
    for i in range(L, N + 1):
        for j in range(N - i + 1):
            total_cost = sum(costs[j:j + i])
            average = total_cost / i
            averages.append(average)
    return min(averages)

def main():
    C = int(sys.stdin.readline())
    solutions = []

    for _ in range(C):
        N, L = map(int, sys.stdin.readline().split())
        costs = list(map(int, sys.stdin.readline().split()))

        min_average = calculate_min_average_cost(N, L, costs)
        solutions.append(min_average)

    for solution in solutions:
        print('%.11f' % solution)

if __name__ == "__main__":
    main()

테스트 케이스에 대하여 기대한 값이 출력되기는 했지만, 시간 초과였다.

---

📝 2차 시도

• 1차 시도에서는 중첩된 루프에서 sum 함수를 반복적으로 호출하였는데, 2차 시도에서는 특정 구간의 합을 보다 효율적으로 계산하기 위하여 부분 합을 사용하였다.

• 2차 시도에서는 min_average라는 변수를 도입하여 각 반복에서 리스트를 생성하지 않고도 직접 최솟값을 갱신할 수 있도록 하였다.

✨ 소스 코드

import sys

def calculate_min_average_cost(N, L, costs):
	# 부분 합 배열
    partial_sums = [0] * (N + 1)

	# 부분 합 계산
    for i in range(1, N + 1):
        partial_sums[i] = partial_sums[i - 1] + costs[i - 1]

	# 최소 평균 비용 초기화
    min_average = float('inf')

    for i in range(L, N + 1):
        for j in range(N - i + 1):
            total_cost = partial_sums[j + i] - partial_sums[j]
            average = total_cost / i
            min_average = min(min_average, average)

    return min_average

def main():
    C = int(sys.stdin.readline())
    solutions = []

    for _ in range(C):
        N, L = map(int, sys.stdin.readline().split())
        costs = list(map(int, sys.stdin.readline().split()))

        min_average = calculate_min_average_cost(N, L, costs)
        solutions.append(min_average)

    for solution in solutions:
        print('%.11f' % solution)

if __name__ == "__main__":
    main()