[백준] 2003 수들의 합- Java

📌 문제 정보

• 출처: 문제 링크
• 난이도: ⭐
• 문제 유형: 완전 탐색
• 사용 언어: Java 

---

🔍 문제 설명

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

---

💡 풀이 노트

완전 탐색 

• 모든 구간의 합을 일일히 계산해야 함
• 시간복잡도 O(N²)

---

🚀 코드 (Java)

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        int cnt = 0;
        // 완전 탐색: 모든 구간 [i, j]에 대해 합을 계산
        for (int i = 0; i < N; i++) {
            int sum = 0;
            for (int j = i; j < N; j++) {
                sum += arr[j];
                if (sum == M) {
                    cnt++;
                    break; 
                }
            }
        }
        System.out.println(cnt);
    }
}

---

🖥 실행 결과

입력

4 2
1 1 1 1

 

출력

3

---

입력

10 5
1 2 3 4 2 5 3 1 1 2

 

출력

3

---

🔄 개선 가능성

투 포인터

• 한 번씩만 탐색 → 효율적
• 시간 복잡도 O(N)

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }

        int cnt = 0;

        int start = 0, end = 0, sum = 0;
        while (true) {
            if (sum < M) {
                if (end == N) break;
                sum += arr[end++];
            } else {
                if (sum == M) cnt++;
                sum -= arr[start++];
            }
        }
        System.out.println(cnt);
    }
}

while (true) {
    if (sum < M) {
        if (end == N)
       		break;
        sum += arr[end++];
    }
    else {
    	if (sum == M)
    		cnt++;
    	sum -= arr[start++];
    }
}

• 구간의 합이 `M`보다 작다면 `end` 값을 늘려서 구간을 오른쪽으로 확장
  • 만약 `end`가 `N`까지 도달했다면 더 이상 확장 불가능 → 반복 종료
• 합이 `M` 이상이라면:
  • 같다면 `cnt`를 증가시킴
  • 크다면 구간을 줄이기 위해 `start`를 오른쪽으로 이동

---

📌 깃허브 코드 저장소: https://github.com/glorypang/CodingTest