[BOJ] 2003. 수들의 합2

이 문제는 두개의 포인터를 움직이며 구간을 구하는 투포인터를 사용하는 문제이다.

투포인터는 low, high 두지점을 0 부터 시작하여 특정조건에 따라 움직이는 알고리즘이다. 이 문제에선 구간합이기에 sum이라는 변수를 이용하여 low, high를 움직여준다. 다음과 같은 조건 While루프를 움직인다.
1-1. 구간합 sum이 목표 M보다 크거나 같다면 sum-=arr[low], low++
1-2. high가 맨끝인 N과 같다면 break
1-3. 구간합 sum이 목표 M보다 작다면 sum+=arr[high], high++
2. 구간합이 sum이 목표 M과 같다면 구간 [low, high)에서 정답을 가짐

상당히 자주 쓰이는 알고리즘이고 활용 N^2을 N으로 줄이는 알고리즘이기에 숙달이 필요할것 같다. 유사한 알고리즘으로 슬라이딩 윈도우가 있는데 차이점은 슬라이딩 윈도우는 크기 N만큼 고정한상태로 움직이는 것이고, 투포인터는 크기가 자유롭게 움직이는 점이다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_2003_수들의합2 {
    static int N;
    static int[] arr;
    static long M;
    
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        st=new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Long.parseLong(st.nextToken());
        
        
        st=new StringTokenizer(br.readLine());
        arr=new int[N];
        for(int i=0;i<N;i++)
            arr[i]=Integer.parseInt(st.nextToken());
        
        
        answer=0;
        twoPointer();
        System.out.println(answer);
        
    }
    static void twoPointer() {
        int high=0;
        int low=0;
        
        long sum=0;
        
        while(true) {
            if(sum>=M) {    //합이 더클때
                sum-=arr[low];
                low+=1;
            }else if(high==N) {        //high가 맨끝점에 갔을때
                break;
            }if(sum<M) {    //합이 작을때
                sum+=arr[high];
                high+=1;
            }
            
            if(sum==M) {        //[low, high) 를가짐
                answer+=1;
            }
        }
    }
}