[Algospot] 알고스팟 FESTIVAL 록 페스티벌

출처: https://algospot.com/judge/problem/read/FESTIVAL 

 Input 

2

6 3

1 2 3 1 2 3

6 2

1 2 3 1 2 3

 

 Output 

1.75000000000

1.50000000000

 

for문을 이용한 완전 탐색

L개의 팀이 확보된 상태이고 하루에 한 팀만이 공연할 수 있기에

L ~ N개만큼 공연장을 대여해야 합니다.

 

연속된 일자라는 조건이 있기 때문에 for문을 통해서 

시작일과 총 예약일수를 변화해가면 평균 대여 비용을 구합니다.

 

※ 출력 형식을 맞추기 위해 아래와 같이 출력(double형)

System.out.println(String.format("%.12f",result));

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.next());
         
        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(sc.next());
            int L = Integer.parseInt(sc.next());
             
            int[] days = new int[N];
            for(int j=0; j<days.length; j++) {
                days[j] = Integer.parseInt(sc.next());
            }
             
            double sum = 0;
            for(int j=0; j<L; j++) {
                sum += days[j];
            }
            double result = sum / L;
             
            int start_day = 0;
            while(true) {
                 
                // 최소 연속일자로 더 이상 만족할 수 없으면 탐색 종료
                if(start_day + L > days.length) {
                    break;
                }
                 
                // 일자를 늘려가면 평균 대여 비용을 산출한다.
                int extend_day = 0;
                while(true) {
                    sum = 0;
                    // 배열을 초과하지 않는 범위에서
                    int end_day = start_day + L + extend_day;
                     
                    // 탐색을 멈추고 공연 시작일자를 바꿔야 된다.
                    if(end_day > days.length) break;
                     
                    for(int j=start_day; j<end_day; j++) {
                        sum += days[j];
                    }
 
                    if(sum / (end_day -start_day) < result) result = sum / (end_day - start_day);
                 
                    // 하루하루 대여 일자를 늘려본다.
                    extend_day++;
                }
                 
                // 시작일자를 바꾼다.
                start_day++;
            }
            System.out.println(String.format("%.12f",result));
        }
    }
}