[백준] 2003 수들의 합2

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

2021-01-05

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main2003 {
    public static int N, M, arr[], answer;
    
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        answer = 0;
        
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        
        int start = 0;
        int end = 0;
        int sum = 0;
        
        while(start < N) {
            if(sum >=M) sum -= arr[start++]; // sum이 M보다 커졌을 때, 새로운 현재 값을 빼주고, start를 한칸 앞으로 이동한다. 
            else if(end == N) break;
            else sum += arr[end++]; //(sum이 M보다 작을 떄) sum에 새로운 현재 값을 더해준 후, end 포인터를 한 칸 이동
            
            if(sum == M) answer++; // sum이 M과 같은 값일 때 
        }
        
        System.out.println(answer);
    }
}
 

 

#문제풀이

 

투 포인터(Two Pointers Algorithm)에 대해서 공부하면서 풀어봤다.

 

1. start와 end 두 가지 변수값을 잡아준다. 시작은 두 변수 모두 0에서 시작한다. 

 

2. sum 변수에 배열의 값을 더하거나 빼면서 값을 경우의 수를 찾아준다. 만약 sum의 값이 찾고자 하는 M값보다 작은 경우 end포인터를 계속 뒤로 이동하면서 sum에 값을 더해준다.

 

3. 만약 sum이 원하는 M값을 찾을 경우 answer를 카운트 해준다. 만약 sum이 M보다 커지는 경우는 현재 값을 빼주고 start 포인터를 뒤로 이동한다.

 

4. while문은 start가 N이하일 동안에만 수행되고, end 포인터가 N에 도달하게 되면 수행을 멈춘다.