[백준 2003] 수들의 합 2

 

부분합배열을 만들어도 O(n^2) 으로 시간초과가 난다.

임의의 변수 start, end를 만들어서 start ~ end 의 합과 m을 비교하며 두 변수의 값을 조정하는 방식으로 풀었다.

 

이 방법을 투 포인터라고 한다.

1. start ~ end의 합 sum을 m과 비교한다.

1-1. sum >= m 일때 합을 줄여아하므로 start값을 올려주고 그 값만큼 sum에서 빼준다.

1-2. end가 n일때 배열을 초과하였으므로 정지한다.

1-3. sum < m 일때 합에 수를 더 더해야하므로 end값을 올려주고 그 값만큼 sum에 더한다.

1-4. sum == m 일때 카운트 한다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int s = 0;
        int e = 0;
        int sum = 0;
        int result = 0;
        while(true) {
            if(sum >= m) sum -= a[s++];
            else if(e == n) break;
            else sum += a[e++];
            if(sum == m) result++;
        }
        System.out.println(result);
    }
}