[백준 - 1806] 부분합 - Java

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

1806번: 부분합

 

two pointer를 사용한 간단한 문제이다.

 

low와 high 사이의 합이 C 미만이라면 high를 한 칸 증가시키고, C와 같거나 크다면 minlength를 갱신시키고 low를 한 칸 증가시킨다.

 

 

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 M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }


        int sum = 0, len = Integer.MAX_VALUE;
        int low = 0, high = 0;
        while(high<=N){
            if(sum>=M){
                sum-=arr[low];
                len = Math.min(len, high-low);
                low++;
            }
            else if(high>=N) break;
            else {
                sum += arr[high++];
            }
        }
        System.out.println(len<Integer.MAX_VALUE? len:0);
    }
}