[BOJ] 2003 - 수들의 합 2 JAVA

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1

4 2

1 1 1 1

예제 출력 1

3

예제 입력 2

10 5

1 2 3 4 2 5 3 1 1 2

예제 출력 2

3

 

 

 

 

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[] arr = null;
    static int N, M, ans;

    public static void twoPointer() {
        int L = 0, R = 0;
        int sum = arr[0];

        while(R < N) {
            if(sum < M) {
                R += 1;
                sum += arr[R];
            }else if(sum == M) {
                ans += 1;
                R += 1;
                sum += arr[R];  // R == N이 될 때 인덱스 오류를 방지하기 위해 arr을 [N+1]로 잡고 [N]은 0으로 둔다.
            }else if(sum > M) {
                sum -= arr[L];
                L += 1;
                if(L > R) {  // L == R 인데 그 수가 M보다 크다면 L > R이 되어버림. 이에 대한 처리.
                    R = L;
                    sum = arr[L];
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        twoPointer();
        System.out.println(ans);
    }
}

 

투 포인터 문제.

 

문제를 읽자마자 반사적으로 O(N^2)의 방법이 떠오른다.

N^2 = 1억으로 1초 안에 해결이 가능하지만 문제의 제한시간은 0.5초.

 

투 포인터를 사용한 O(N)으로 해결해야 한다.