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

• 백준 문제 URL

---

문제 요약

주어진 배열에서 연속된 부분 수열의 합이 정확히 target이 되는 경우의 수를 구하는 문제다.

즉,

• 배열 arr에서 어떤 i ≤ j에 대해
• arr[i] + arr[i+1] + ... + arr[j] = target 인 구간의 개수를 반환한다.

---

핵심 아이디어

이 문제는 가변 길이 슬라이딩 윈도우 투 포인터를 사용한다.
프로그래머스 연속 수열과 유사하지만, 최소 길이가 아닌 개수만 세는 점이 다르다.

핵심 로직:
1. sum == target → count++ 후 오른쪽 확장 (다른 구간도 탐색)
2. sum > target → 왼쪽 축소
3. sum < target → 오른쪽 확장

---

알고리즘 핵심 로직

start = 0, end = 0, sum = 0, count = 0
while end < n:
    if sum == target:
        count++  // 현재 구간 발견
        end++    // 다음 구간 탐색 위해 오른쪽 확장
        sum += arr[end]
    elif sum < target:
        end++
        sum += arr[end]
    elif sum > target:
        sum -= arr[start]
        start++

핵심:
sum == target일 때 count만 증가하고 별도로 길이를 추적하지 않는다.

---

전체 코드 (제출용)

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 target = Integer.parseInt(st.nextToken());

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

        int count = 0;
        int startIdx = 0;
        int endIdx = 0;
        int sum = arr[startIdx];

        while (startIdx <= endIdx && endIdx < arr.length) {
            if (sum == target) {
                count++;
                endIdx++;
                if (arr.length == endIdx) break;
                sum += arr[endIdx];
            } else if (sum < target) {
                endIdx++;
                if (arr.length == endIdx) break;
                sum += arr[endIdx];
            } else if (sum > target) {
                sum -= arr[startIdx];
                startIdx++;
                if (startIdx > endIdx) {
                    endIdx++;
                    if (arr.length == endIdx) break;
                    sum += arr[endIdx];
                }
            }
        }
        
        System.out.println(count);
    }
}

---

예제 시뮬레이션

입력:

n = 10, target = 5
arr = [1, 1, 1, 2, 3, 4, 1, 2, 3, 1]

탐색 과정에서 발견되는 구간들:

• [1, 1, 1, 2] (인덱스 0~3, 합 = 5)
• [2, 3] (인덱스 3~4, 합 = 5)
• [1, 4] (인덱스 6~7, 합 = 5)
• [2, 3] (인덱스 7~8, 합 = 5)

최종 결과: 4

---

핵심 포인트 정리

• 합이 정확히 k인 연속 부분 수열 개수 세기
• sum == k 발견 시 count++ 후 오른쪽 확장 (다른 구간 탐색)
• 길이 제약 없음 → 모든 가능한 길이 탐색
• 시간 복잡도: (O(n))

---

비교:

문제	목표	sum == k 동작
연속 수열	최소 길이	왼쪽 축소
수의 합 4	개수	오른쪽 확장

---

+ 꽤나 혼란스러웠던 문제..