[종만북] FESTIVAL - 록 페스티벌 (자바 java)

문제 : FESTIVAL

 

  N이 최대 1000 이므로 O(N^2)의 알고리즘이라도 충분히 통과할 수 있다. 따라서 단순히 차이가 L 이상인 모든 구간에 대해 O(N^2)으로 확인해주면 된다. (코드의 24~25 line 참고)

 

  주의점은 10^(-7) 이하의 절대/상대 오차가 있어야 하므로, 그냥 바로 출력하면 안되고 소수점 8자리 이상을 출력하도록 해야 한다. 자바의 경우 String.format("%.8f", answer)과 같은 코드로(c언어와 비슷한 출력 방식) 소수점 8자리까지 출력할 수 있다.

 

  그리고 모든 구간에 대해 직접 더해봐도 시간 제한에 충분히 맞출 수 있긴 하지만(O(N)), prefix sum을 미리 구해둘 경우 [a, b] 구간의 합은 arr[b]-arr[a-1] 과 같이 O(1)로 구할 수 있다(코드의 7 line).

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private double getAverageFee(int[] prefixSum, int i, int j) {
        int sum = prefixSum[j] - prefixSum[i-1];
        return (double)sum / (j-i+1);
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int c = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (c-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            int[] prefixSum = new int[n+1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                prefixSum[i] = prefixSum[i-1] + Integer.parseInt(st.nextToken());
            }
            double answer = Double.MAX_VALUE;
            for (int i = 1; i <= n-l+1; i++) {
                for (int j = i+l-1; j <= n; j++) {
                    double curAverage = getAverageFee(prefixSum, i, j);
                    if (answer > curAverage)
                        answer = curAverage;
                }
            }
            sb.append(String.format("%.8f\n", answer));
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}