백준 21921 자바

 

처음 이 문제를 풀었을 때는 시간제한 상관없이 누적합의 방식으로만 풀어서 아래와 같은 코드를 작성했다.

시간초과가 날 걸 알았지만 일단 풀어보고 싶었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 days = Integer.parseInt(st.nextToken());
        int during_days = Integer.parseInt(st.nextToken());
        int[] arr = new int[days];

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

        int start = 0;
        int end = during_days-1;
        int cnt = 0;
        int sum = 0;
        int new_sum;
        for (int i = start; i <= end; i++) {
            sum +=  arr[i];
        }

        while (true) {
            new_sum=0;
             start++;
             end++;

            if (end == arr.length) break;

            for (int i = start; i <= end; i++) {
                 new_sum += arr[i];
            }


          if (sum < new_sum) {
              sum = new_sum;
              cnt=1;
          } else if (sum == new_sum) {
              cnt++;
          }

        }

        if (sum == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(sum);
            System.out.println(cnt);
        }
    }
}

 

구글링을 통해 슬라이딩 윈도우 방식에 대해 알아보았고 start와 end를 자유롭게 움직이는 누적 합과 달리 일정한 간격으로 움직이는 방식이라는 것을 알게 되었다.

 

import java.io.InputStreamReader;
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 days = Integer.parseInt(st.nextToken());
        int during_days = Integer.parseInt(st.nextToken());
        int[] arr = new int[days];

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

        int sum = 0;
        for (int i = 0; i < during_days; i++) {
            sum += arr[i];
        } 

        int max = sum;
        int cnt = 1;

        for (int i = 0; i < days - during_days; i++) {

            sum += arr[i+during_days];
            sum -= arr[i];

            if (sum == max) {
                cnt++;
            }

            if (sum > max) {
                cnt = 1;
                max = sum;
            }
        }

        if (max == 0) {
            System.out.println("SAD");
        } else {
            System.out.println(max);
            System.out.println(cnt);
        }
    }
}