[ 백준 2003 / Java ] 수들의 합 2

https://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

문제 설명

예제 2번으로 설명

문자열 개수: 10

찾는 숫자: 5

1 2 3 4 2 5 3 1 1 2

 

투 포인터

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스 0을 가리키도록 한다.
2. 현재 부분 합이 찾는 수와 같다면, 카운트한다. 현재 start 값을 빼주고 start 인덱스를 1 증가시킨다.
3. 현재 부분 합이 찾는 수보다 작다면 현재 end 값을 더하고 end 인덱스를 1 증가시킨다.
4. 현재 부분 합이 찾는 수보다 크다면, 현재 start 값을 빼주고 start 인덱스를 1 증가시키다.
5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class addnums2 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
 
        int n = Integer.parseInt (st.nextToken()); //10
        int m = Integer.parseInt(st.nextToken()); //5
 
        int[] arr = new int[n];
 
        st = new StringTokenizer(reader.readLine()); //1 2 3 4 2 5 3 1 1 2
        for (int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int intervalSum = 0; //5가 될때 count 해준다
        int count = 0;
        int end = 0;
 
        for (int start=0; start<n; start++) {
            while (intervalSum < m && end < n) {
                intervalSum += arr[end++]; //#1 -- 처음: 1로 시작 //두번째: 1+2 //세번째: 1+2+3 => 6이 5보다 크므로 start값을 빼준다.
            }
            if (intervalSum == m) { //#3 -- count = 1
                count++;
            }
            intervalSum -= arr[start]; //#2 -- 6 - 1 = 5가 되었다!
        }
        System.out.println(count); //#4 -- 마지막에는 3이 나온다
    }
}
 

 

다른게 풀어본 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N,M;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(twoPointer(arr, M));
    }
    static int twoPointer (int[] arr, int m) {
        int count = 0;
        int low = 0;
        int high =0;
        int sum = 0;
        int len = arr.length;
        while(true) {
            if (sum >= m) {
                sum -= arr[low++];
            } else if (high >= len) {
                break;
            } else {
                sum+= arr[high++];
            }
            if (sum == m) {
                count++;
            }
        }
        return count;
    }
}