<두 포인터> BOJ 2003 수들의 합 2

문제

부분 수열의 합이 M이 되는 경우의 수를 구하는 문제이다.

개념

두 포인터를 다루는 기본적인 문제로 개념 설명을 하도록 하겠습니다.

• 두 포인터를 사용하기 위한 조건
  1. 포인터 i가 움직이면 작아져야 한다.(구간의 합이)
  2. 포인터 j가 움직이면 커져야 한다.(구간의 합이)
  3. 결국 수열 중에 음수가 존재하면 안된다.
• 두 포인터의 조건문
  0. sum은 i-j 구간의 합을 의미
  1. sum < m -> j를 오른쪽으로 움직인다.
  2. sum >= m -> i를 오른쪽으로 움직인다.
• i와 j의 위치를 고려하지 않고 i를 오른쪽으로 움직여서 j보다 커지면 어쩌나?
  그렇다고 하더라도 다시 j가 움직여야 하는 상황이 되므로 걱정하지 않아도 된다.
• 두 포인터의 효과
  두 포인터를 사용하면 복잡도를 얼마나 줄일 수 있을까?
  • 두 포인터를 사용하면 $O(N+N)$의 복잡도로 $O(N^2)$ 복잡도의 효과를 얻을 수 있다. 즉 2중 for문을 돌린 것과 동일한 결과를 낸다.
  • sum < m의 경우 중 sum의 최대 값은 구간의 합이 m보다 작은 값 중 최대값이다.
  • sum >= m의 경우 중 sum의 최소 값은 구간의 합이 m보다 크거나 같은 값 중 최소값이다.

코드

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

class baek__2003 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");

        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        int[] nums = new int[n];

        temp = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(temp[i]);
        }

        int i = 0;
        int j = 0;

        int cnt = 0;
        int sum = nums[0];
        while (true) {
            if (sum == m)
                cnt++;
            if (sum < m) {
                j++;
                if (j == nums.length)
                    break;
                sum += nums[j];
            } else {
                sum -= nums[i];
                i++;
            }
        }

        System.out.print(cnt);
    }
}