[Java] 백준 1549번 K

누적합 문제입니다.

수열이 주어집니다.
[연속한 k개의 수1]와 [연속한 k개의 수2]의 차가 가장 적은 값을 구해야합니다.
위의 [연속한 수1] [연속한 수2]는 겹치면 안되며, 적은 값이 여러개면 k를 최대인것으로 출력합니다.

누적합을 구해준후에 브루트포스로 모든 경우의수를 확인했습니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    int n = Integer.parseInt(br.readLine());
    long[] arr = new long[n + 1];
    int k = 0;
    long min = Long.MAX_VALUE;

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

    for (int i = 1; i <= n / 2; ++i) {
      for (int j = i; j <= n; ++j) {
        for (int l = j + i; l <= n; ++l) {
          long sub = Math.abs((arr[j] - arr[j - i]) - (arr[l] - arr[l - i]));
          if (sub <= min) {
            min = sub;
            k = i;
          }
        }
      }
    }

    bw.write(k + "\n");
    bw.write(min + "\n");
    bw.close();
  }
}