[BOJ] 2003. 수들의 합2 (🥈, 투 포인터)

🔗

풀이

투 포인터로 풀이했다. 2개의 포인터가 있다고 가정하고, p1 ~ p2까지의 값을 모두 합한 값을 sum 에 저장하게 되는데 p1과 p2를 적당히 조절해서 목표값을 맞출 수 있는 경우의 수가 몇개나 되는지 찾는 문제이다.

시작은 p1과 p2의 위치가 동일하다. 모든 수는 자연수이므로 합은 0보다 낮을 수 없다. sum이 해당 목표값보다 작은 값이라면 p2에 있는 값을 더하고 p2를 1증가시킨다.

이제 sum은 1이 됐다. 하지만 목표값인 2보다는 작다. 다시 p2에 있는 값을 더한다.

이제 sum은 목표값이 되었다. answer를 증가시켜주게 된다.

해당 합이 목표값에 도달하게 되거나, 그 값을 넘어서게 되면 속하는 값들을 빼줘야 한다. 이때 p1을 이용한다. p1에 있는 값을 빼주고 p1을 증가시킨다.

해당 과정은 p2의 값이 배열의 인덱스를 넘어서게 되었는데 sum이 목표값보다 작을 때까지 진행된다. 목표값보다 크다면 p1을 증가시켜서 계속 빼주면 되지만 목표값보다 크면 p2을 계속 증가시켜야 하는데 이는 불가능하기 때문이며 더 증가시켜봤자 가능한 경우의 수가 없기 때문이다.

package Baekjoon.Silver;

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

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

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

        int p1 = 0; int p2 = 0;
        int sum = 0;
        int answer = 0;

        while (!(sum < M && p2 >= N)) {
            if (sum == M) answer++;
            
            if (sum >= M) {
                sum -= arr[p1];
                p1++;
            } else {
                sum += arr[p2];
                p2++;
            }
            System.out.println(p1 + " " + p2 + " " + sum);
        }
        System.out.println(answer);
    }
}