[백준] 21921번. 블로그 (JAVA)

https://www.acmicpc.net/problem/21921

---

문제

 

---

풀이

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

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

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int sum = 0;
        for (int i = 0; i < x; i++) sum += arr[i];

        int max = sum;
        int maxCnt = 1;
        for (int i = x; i < n; i++) {
            sum += arr[i] - arr[i-x];
            if (max == sum) maxCnt++;
            else if (max < sum) {
                max = sum;
                maxCnt = 1;
            }
        }
        if (max == 0) {
            System.out.println("SAD");
            return;
        }
        System.out.println(max + "\n" + maxCnt);

    }
}

 

문제 난이도 자체는 실버 3 답게 그렇게 어렵지 않은 편이라고 생각한다.

다만, 투포인터 그 중에서도 슬라이딩 윈도라는 것을 깨닫지 못하면 시간초과(25000 x 8000)에 걸릴 수 있음에 유의해야 한다.

 

동일한 간격의 크기를 비교하는 것이기 때문에 한 칸씩 미뤄가며 계산한다. 이 전의 빠지는 값이 새로 추가되는 값보다 작다면, 총합은 커지게 된다. 우리는 그 값을 추적하며 값이 같을 때 카운트 값만 증가시켜 주면 된다.