문제 링크

풀이

매번 X일 동안의 방문자 수의 합을 계산하면 중복된 연산이 많아지고 시간 초과가 발생하게 된다. (최대 $8,000 * 250,000 = 2 * 10^9$ 번)

따라서 슬라이딩윈도우 알고리즘을 사용하여 방문자 수의 합을 계산한다. X일의 범위를 유지하면서 하루씩 뒤로 밀며 계산하는 것을 의미한다.

X가 3일 때, 1일 2일 3일의 합(sum)을 구하고, 그 이후의 2, 3, 4일의 합을 구할 때는 sum에서 1일째 방문자 수를 뺀 후 4일째의 방문자를 더해준다. 3,4,5일의 합을 구할 때는 마찬가지로 4일을 2일을 빼고, 5일째 방문자 수를 더하면 된다.

sum = sum - visitor[i - x] + visitor[i];

위 코드에서
visitor[i - x]는 윈도우에서 빠져나가는 값, visitor[i]는 새로 들어오는 값이 되는 것이다.

위 방식으로 X일 동안의 방문자 수의 합을 반복문을 돌며 구하고, 최댓값을 갱신한다. 최댓값과 동일한 방문자 수 합이 나오면 그 기간의 수도 갱신하여준다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol21921 {
    static int n, x;
    static int[] visitor;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());

        visitor = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            visitor[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        for (int i = 1; i <= x; i++) {
            sum += visitor[i];
        }

        int maxSum = sum;
        int count = 1;
        for (int i = x + 1; i <= n; i++) {
            sum = sum - visitor[i - x] + visitor[i];
            if (sum > maxSum) {
                maxSum = sum;
                count = 1;
            } else if (sum == maxSum) {
                count++;
            }
        }
        if (maxSum == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(maxSum);
            System.out.println(count);
        }
    }
}