[백준 1806] 부분합 자바 //le_effort//

부분합을 구하는 문제이다

N이 100,000 으로써 일반적인 2중반복문을 한다면 O(N^2)으로 1초안에 들어오지 못해 오답을 받는다.

이를 해결하기 위해선 투포인터 알고리즘을 쓰면 된다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,s;
    static int arr[];
    static int cnt=0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        s = Integer.parseInt(t[1]);
        arr = new int[n];
        String[] tt = br.readLine().split(" ");
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(tt[i]);
        }
        int start = 0;
        int end =0;
        int sum=0;
        int min = Integer.MAX_VALUE;
        while(true) {
            if(sum>=s) {
                //System.out.println(end+" "+start);
                sum-=arr[start++];
                min = Math.min(min, end-start+1);
                //start++;
            }
            else if(end == n) {
                if(min==Integer.MAX_VALUE) {
                    System.out.println(0);
                }
                else {
                    System.out.println(min);
                }
                break;
            }
            else {
                sum+=arr[end++];
            }
        }
        
    }
}