[BOJ] 1806 부분합 (JAVA)

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

1806번: 부분합

머리와 꼬리의 인덱스를 저장하고 그 사이에 있는 값들의 합을 구해야 합니다.

합이 S보다 크거나 같으면 꼬리를 한 칸 당겨오고, 작으면 머리를 앞으로 한 칸 뻗습니다.

 

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		int[] input = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		} // end of input
		
		int head = 0;
		int tail = 0;
		int sum = input[0];
		int len = 123456;
		
		while(len != 0) {
			
			if(S <= sum) {
				len = Math.min(len, head - tail);
				sum -= input[tail++];
			} else if(head + 1 < N) {
				sum += input[++head];
			} else break;
			
		}
		
		System.out.print(len == 123456 ? 0 : len + 1);
		
	}
	
}