[BOJ] 2003번 수들의 합 2 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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[] A;

    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());

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

        int cnt = 0;
        int left = 0;
        int right = 0;
        int sum = A[left];
        while (left < N) {
            // 현재 합이 M 보다 크거나 같으면 왼쪽 포인터 이동
            if (sum >= M) {
                // 같으면 cnt 값 증가
                if (sum == M) {
                    cnt++;
                }
                sum -= A[left];
                left++;
            } else {
                // 현재 합이 M 보다 작으면 오른쪽 포인터 이동
                right++;
                if (right >= N) {
                    break;
                }
                sum += A[right];
            }
        }
        System.out.println(cnt);
    }
}

📄 해설

접근

• 투 포인터 기본문제.
• 투 포인터 알고리즘에 대한 학습을 진행한다면 어렵지 않게 해결할 수 있음

과정

• 코드를 보면 바로 이해가 가능할 것
• left 포인터의 위치가 N 이상이 될 때까지 반복 수행하고, 각 포인터를 이동할 때마다 현재 합인 sum 에 해당 위치의 값을 더한다.
• 현재 합이 M 보다 크거나 같다면 left 포인터를 이동시키고, 같다면 cnt 값을 증가시킨다. left 포인터가 이동했다면, 현재 합에서 해당 위치의 값을 제외한다.
• 현재 합이 M 보다 작다면 right 포인터를 이동시킨다. 이때, right 포인터의 값이 N보다 커질 수 있으므로, 이를 체크해준다.