[백준] 2003번 수들의 합 2 - Java, 자바

난이도

실버 3

문제

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

풀이

처음에 이중 반복문으로 풀면되겠지 해서 풀었는데 맞았다.
하지만 이 문제는 이중 반복문으로 푸는 문제가 아닌 투포인터를 푸는게 정석적인 풀이였다. 여기서 조금만 응용된 문제가 나온다면 시간초과 나와서 틀렸을 것이다.

투포인터는 배열의 특정 연속된 구간을 처리하는 경우 O(N)으로 풀 수 있는 아주 유용한 개념이다.

ex) 구간합 문제(2003번, 1806번, 1644번)

구간합 관련 문제가 나온다면 투포인터를 떠올려서 적용하자.

< 투포인터 핵심 로직 >

    int sum=0;
    int start=0,end=0,count=0; // start, end 초기 인덱스를 0으로 지정 

       	while(true){
            if(sum>=m){ // 합이 m보다 크거나 같다면
                sum-=arr[start++]; // 값을 빼주고 start++한다 
            }
            else if(end==n){ // end가 맨 끝에 도착했을 경우 
                break; // 반복문을 끝낸다 
            }else{//  합이 m보다 작으면 
                sum+=arr[end++]; // 값을 더해주고 end++한다 
            }

            if(sum==m){
                count++; // sum과 m이 일치하는 경우 count를 증가시킨다 
            }
        }
        ```


### 코드 
``` java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_2003 {
    public static void main(String[] args) throws IOException {
        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());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        int sum=0;
        int start=0,end=0,count=0;

        while(true){
            if(sum>=m){
                sum-=arr[start++];
            }
            else if(end==n){
                break;
            }else{
                sum+=arr[end++];
            }

            if(sum==m){
                count++;
            }
        }
        System.out.println(count);

    }
}

참고
https://www.youtube.com/watch?v=rI8NRQsAS_s