아이디어

• 오른쪽으로 범위를 늘리다가, 부분합이 $S$ 이상이 되면 왼쪽 끝에서부터 부분합에서 반대로 빼보며 길이를 얼마나 낮출 수 있는 지 본다.
• 만약 부분합이 전체 합이라도 $S$ 이상이 되지 못하면 "0"을 출력한다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, S, A[], sum, ans;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		S = Integer.parseInt(tk.nextToken());

		A = new int[N];
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<N; i++)
			A[i] = Integer.parseInt(tk.nextToken());
		
		ans = Integer.MAX_VALUE;
		sum = A[0];
		
		int q = 0;
		for (int p=0; p<N; p++) {
			while (q < N-1 && sum < S) sum += A[++q];
			if (sum < S) break;
			ans = Math.min(ans, q - p + 1);
			sum -= A[p];
		}
		
		if (ans == Integer.MAX_VALUE)
			ans = 0;
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 23820 KB
• 시간: 284 ms

리뷰

• 투 포인터 문제도 봐야겠다.
• 알고리즘 안 보고 풀기 연습