BOJ : 2003

1. 문제

 

2. 문제 분석 및 알고리즘 설계

 

N개의 수의 나열에서 구간의 합이 M과 같은 경우의 수를 구하는 문제이다.

앞에서부터 머리와 꼬리를 정해두고 머리가 앞으로 나가다가 M보다 커지면 꼬리를 당겨서 푸는 식이다.

그렇다. 투포인터 문제이다.

 

ex) N = 7, M = 5일때

1

2

3

4

2

5

3

  ↑ ptr2                        ↑ ptr1

이렇게 구간의 합이 M을 넘어갈 경우

1

2

3

4

2

5

3

                  ↑ ptr2       ↑ ptr1

이렇게 ptr2를 당겨주면서 다시 합을 확인한 뒤 맞을 경우 result++

 

3.  코드

package week8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q2003_boj {
    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());

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

        int ptr1=0, ptr2=0, result=0, sum=0;

        while (ptr1 < N){
            if(sum > M || ptr2 == N){
                sum -= arr[ptr1];
                ptr1++;
            }else{
                sum += arr[ptr2];
                ptr2++;
            }

            if(sum == M){
                result++;
            }
        }

        System.out.println(result);
    }
}

 

4. 시간 복잡도

 

O(N)

 

5. 결과