[JAVA]백준 2003번: 수들의 합

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

2003번: 수들의 합 2

1. 문제 설명

 

N(1 <=N <=10,000) 개로 된 수열 A [1],.. A [N]이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A [i]+A [i+1]+.... A [j]가 M(1 <=M <=300,000,000)이 되는 경우의 수를 구하는 문제.

 

2. 풀이

 

전형적인 투포인터 문제이다.

 

시작 index를 가리키는 start와 끝 index를 가리키는 end를 선언하여 누적합을 구하는 방식으로 경우의 수를 구한다.

 

투 포인터 방식을 사용하면 O(N)의 시간복잡도를 가진다.

 

*로직

• 현재까지의 누적합이 M보다 작다면 A[end]값을 sum에 더하고 end값을 증가시킨다.
  • 만약 end값이 N과 같다면 연산을 수행하지 않고 종료한다.
• 현재까지의 누적합이 M보다 크다면 A[start] 값을 sum에 빼고 start 값을 증가시킨다.
• 현재까지의 누적합이 M과 같다면 경우의 수를 증가시키고, A [start] 값을 sum에 빼고, start 값을 증가시킨다.

 

3. 코드

import java.awt.*;
import java.io.*;
import java.util.*;

public class Main {

    public static int N, M;

    public static int[] list;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        list = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < N; x++) {
            list[x] = Integer.parseInt(st.nextToken());
        }


        while (end <= N) {
            if (sum == M) {
                // 현재까지 누적 합이 M과 같은 경우
                ans++;
                sum -= list[start++];
            } else if (sum < M) {
                // 현재까지의 누적 합이 M보다 작은 경우

                if(end==N)
                    break;
                sum += list[end++];
            } else {
                // 현재까지의 누적 합이 M보다 큰 경우
                sum -= list[start++];
            }
        }

        System.out.println(ans);




    }






}