1806

 

부분합 : https://www.acmicpc.net/problem/1806

 

이전에 풀었던 문제와 크게 다를것은 없다.

다만 속도를 위해 while문을 활용하여 빠르게 합을 구해주는 trick을 활용한다.

(2-point 알고리즘에서 항상 주의 해야되는 것은 변수의 범위를 잘 설정하는 것이며

기본틀은 머리속에 항상 있어야 한다.)

 

while (sum < S && rt <= N) {
sum += arr[rt++];
}
while (sum > S && lt < rt) {
sum -= arr[lt++];

 

 

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

public class Main {

	static int N, S, answer = Integer.MAX_VALUE;
	static int[] arr;
	private static boolean DBG = false;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new int[N + 5];//IndextError가 발생하지 않도록 적당히 큰 배열 선택
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int lt = 0, rt = 0;
		int sum = 0, cnt = 0;
		while (rt <= N) {
			
			while (sum < S && rt <= N) {
				sum += arr[rt++];
			}
			while (sum > S && lt < rt) {
				sum -= arr[lt++];

				if (DBG)
					System.out.printf(">[%d %d] answer : %d\n", lt, rt, answer);
				answer = Math.min(answer, rt - lt + 1);
			}

			if (sum == S) {
				sum -= arr[lt++];
				if (DBG)
					System.out.printf("=[%d %d] answer : %d\n", lt, rt, answer);
				answer = Math.min(answer, rt - lt + 1);
			}

		}
		System.out.println(answer==Integer.MAX_VALUE ? 0 : answer);
	}

}