알고스팟 록 페스티벌(festival) 문제 파이썬으로 풀기

공연장을 빌리는 평균 비용을 최소한으로 하는 문제이다.

이 문제를 풀 때 세번의 큰 과정을 거쳐서 정답을 얻게 되었는데, 처음과정은

출처: https://stb95.tistory.com/1

이렇게 대여하는 날짜를 다르게 하여 평균 비용을 구하는 것이다. 이 방법이 제일 구현하기 간단하고 쉽게 생각할 수 있어서 해보았지만, 시간초과가 나왔다.

출처: https://stb95.tistory.com/1

그래서 해본 것이 이렇게 시작하는 날짜를 정하고 대여하는 날짜를 늘려나가는 방식이다. 이건 전의 방법보다 빠르겠지만, 코드를 짰을때 여전히 시간초과가 났다.

그 원인이 뭘까 하고 생각해보니, 대여비용을 구할때 썻던 sum 함수가 의외로 시간을 많이 잡아먹는다는 글을 보았다. 그래서 sum의 사용을 최소한으로 하려 코드를 다시 짰고, 드디어 정답을 얻게 되었다.

#festival
import sys
 
 
case = int(sys.stdin.readline())
for i in range(case):
    n, l = map(int, sys.stdin.readline().split())  # n=대여일 수, l=공연팀 수
    borlist = list(map(int, sys.stdin.readline().split()))  # 대여비용 입력받음
    minlist = []  # 평균비용들 저장
    for t in range(n - l+1):  # t=시작하는 날
        initsum = sum(borlist[t:t+l])  # t부터 t+l-1날까지의 비용의 합(sum의 사용을 최소로 함)
        minlist.append(initsum/l)  # t부터 t+l-1날까지의 비용의 평균을 넣는다
        for j in range(n-l-t):
            initsum += borlist[t + l + j]  # 다음 날의 비용을 더하고
            localresult = initsum / (l + j+1)  # 날이 늘어난 만큼 더해 나눈다
            minlist.append(localresult)
    result = min(minlist)  # 최소값을 찾는다
    print("%.11f" % result)  # 출력
 

sum을 매번 쓰지 않고, 시작날짜를 정할때만 쓰는 코드이다.

수행시간이 길긴한데, 문제에서 주는 제한이 20초라 6초도 통과 가능하다.

 

 

느낀점:

1. sum과 같은 함수가 시간을 많이 잡아먹기도 하는구나.. 시간 제한 때문에 신경써야 할 부분인거같다.

2. 정답률이 23%인데 나는 7번만에 성공했다. 1/7이면 확실히 23%보단 낮은데.. 분발해야겠다.