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

김민석·2021년 2월 24일
0

알고리즘

목록 보기
12/27

문제

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

개념

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

  • 두 포인터를 사용하기 위한 조건
    1. 포인터 i가 움직이면 작아져야 한다.(구간의 합이)
    2. 포인터 j가 움직이면 커져야 한다.(구간의 합이)
    3. 결국 수열 중에 음수가 존재하면 안된다.
  • 두 포인터의 조건문
    1. sum은 i-j 구간의 합을 의미
    2. sum < m -> j를 오른쪽으로 움직인다.
    3. sum >= m -> i를 오른쪽으로 움직인다.
  • i와 j의 위치를 고려하지 않고 i를 오른쪽으로 움직여서 j보다 커지면 어쩌나?
    그렇다고 하더라도 다시 j가 움직여야 하는 상황이 되므로 걱정하지 않아도 된다.
  • 두 포인터의 효과
    두 포인터를 사용하면 복잡도를 얼마나 줄일 수 있을까?
    • 두 포인터를 사용하면 O(N+N)O(N+N)의 복잡도로 O(N2)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);
    }
}
profile
누구나 실수 할 수 있다고 생각합니다. 다만 저는 같은 실수를 반복하는 사람이 되고 싶지 않습니다. 같은 실수를 반복하지 않기 위해 기록하여 기억합니다.🙃

0개의 댓글