[백준/Java] 2003-수들의 합2

2003-수들의 합2

문제 바로가기

문제

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

요구사항

N개의 수로 된 수열 $A[1], A[2], ..., A[N]$이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 $A[i] + ... + A[j]$가 $M$이 되는 경우의 수를 구해야 한다.

입력 제한
$1 \le N \le 10,000$
$1 \le M \le 300,000,000$
시간 제한: 0.5초

핵심 포인트시간 제한이 0.5초로 매우 짧다. 단순한 이중 반복문($O(N^2)$)으로 구간 합을 구하면 연산 횟수가 많아져 시간 초과가 발생할 위험이 크다. 따라서 $O(N)$의 시간 복잡도를 가지는 알고리즘을 사용해야 한다.

접근 방식

이 문제는 연속된 부분 수열의 합을 구하는 문제이며, 모든 수는 자연수이다. 이럴 때 가장 효율적인 방법이 바로 투 포인터(Two Pointers) 알고리즘이다.

알고리즘 로직
start와 end라는 두 개의 포인터를 사용하여 구간의 길이를 유동적으로 조절하며 합을 찾는다.

초기 상태: start = 0, end = 0, sum = 0

탐색 (While Loop):

sum >= M: 현재 구간 합이 목표값보다 크거나 같다면, 값을 줄여야 한다. -> sum에서 arr[start]를 빼고 start를 1 증가시킨다.

end == N: 더 이상 더할 숫자가 없고, 위에서 start를 줄이는 작업도 끝났다면 반복을 종료한다.

sum < M: 현재 구간 합이 목표값보다 작다면, 값을 더 키워야 한다. -> sum에 arr[end]를 더하고 end를 1 증가시킨다.

카운트: 매 계산 후 sum == M이면 정답 카운트를 1 증가시킨다

💡 주의할 점 (삽질 포인트)
start와 end를 조작하는 순서가 매우 중요하다. 만약 end가 배열의 끝(N)에 도달했다고 해서 반복문을 바로 break 해버리면 안 된다. end가 끝에 도달했더라도, 현재 sum이 M보다 크다면 start를 줄여서 M을 만들 수 있는 경우의 수가 남아있기 때문이다.

따라서, sum >= M인 경우를 먼저 체크해서 start를 움직이게 하고, 그 다음에 end의 범위를 체크해야 모든 경우를 빠짐없이 탐색할 수 있다.

코드

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


public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 1, end = 1;
        int sum = 0;
        int answer = 0;
        while (true) {
            if (sum >= m){
                sum -= arr[start++];
            }
            else if(end > n) {
                break;
            }
            else {
                sum += arr[end++];
            }

            if(sum ==m) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

느낀점

누적 합 vs 투 포인터처음에는 [11659번: 구간 합 구하기 4] 문제처럼 누적 합(Prefix Sum) 배열을 미리 만들어두고 arr[i] - arr[j] 형태로 풀려고 시도했었다. 그 방법도 $O(N^2)$으로 풀리긴 하지만, 시간 제한이 빡빡한 이 문제에서는 투 포인터가 훨씬 적합한 정석 풀이였다.

누적 합: 구간이 정해져 있고 쿼리가 많을 때 유리 ($O(1)$)
투 포인터: 합이 M이 되는 구간을 직접 찾아야 할 때 유리 ($O(N)$)

while문의 종료 조건과 순서
이번 문제에서 가장 애를 먹었던 부분은 ArrayIndexOutOfBounds 예외와 논리 오류였다. end가 배열의 끝에 닿았을 때 바로 반복문을 종료시켰더니, start를 줄이면서 찾아낼 수 있는 마지막 정답들을 놓치는 반례가 있었다.

"값을 빼야 하는 상황(sum >= m)"을 가장 높은 우선순위로 두고 처리해야, end가 끝까지 간 뒤에도 남은 탐색을 정상적으로 마칠 수 있다는 것을 배웠다. 알고리즘 로직을 짤 때 조건문의 순서가 결과에 큰 영향을 미친다는 점을 다시 한번 깨달았다.