BOJ 1806 부분합

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

1. 입력값을 통해 누적합을 numbers에 세팅한다
2. end를 하나씩 늘려가며 지금까지의 합이 S보다 크면
   start시작인덱스를 뒤로 밀어 범위를 줄여본다
3. 2번에서 줄인범위가 S보다 작아지면 다시 end값을 늘려 S와 비교한다

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

public class Main {

    private static int[] numbers; // 수열 리스트
    private static int S; // 최소합
    private static int N; // N개의 자연수
    private static int answer; // 답

    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());
        answer = N; // 가능한 가장 큰 값으로 미리 세팅 
        S = Integer.parseInt(st.nextToken());

        numbers = new int[N+1];
        st = new StringTokenizer(br.readLine(), " ");
        int start = 0; // 시작인덱스

        for (int i = 1; i <= N; i++) {
            int val = Integer.parseInt(st.nextToken());
            numbers[i] = numbers[i-1]+val; // 지금까지 입력받은 숫자의 합 세팅

            // start+1 인덱스 값 ~ i 인덱스까지의 합이 S보다 크다면
            // start를 뒤로 밀 수 있다 => S보다 작아질때까지 뒤로 밀어서 업데이트
            if(numbers[i]-numbers[start]>=S) { 
                start = getAnswer(start,i);
            }
        }
        // N개의 숫자를 다 더해도 S보다 작다면 0 출력
        if(numbers[N] < S) {
            System.out.println(0);
        }else {
            System.out.println(answer);
        }

    }

    /**start를 최대한 크게 변경하는 함수*/
    private static int getAnswer(int start, int end) {
        for (int i=0; i+start < end; i++) {
            // start+i+1 부터 end번째 숫자의 합이 S보다 크다면 answer 업데이트
            if(numbers[end]-numbers[start+i]>=S) {
                answer = answer>end-start-i? end-start-i:answer;
            }else { //start+i+1부터 end까지의 합이 S보다 작다면 해당 인덱스 리턴
                return start+i;
            }
        }
        // for문 끝나고 return되지 않았다 => start=end가 같은 값 => 1개의 합으로도 S보다 크다
        answer = 1;
        return end;
    }

}