[BOJ] 2003 수들의 합 2 - JAVA

1. 문제

2003번: 수들의 합 2

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

---

2. 풀이

1.  입력받은 뒤 시작지점을 하나씩 뒤로 밀어가면서 탐색한다.

2.  시작지점부터 현재 지점까지 합이 M과 같다면 count를 +1한다.

3.  시작지점부터 현재 지점까지 합이 M보다 크거나 같다면 시작지점을 한 칸 늘려야하므로 멈춘다. 

4.  count를 출력한다.

import java.io.*;
import java.util.*;

public class BOJ_2003_수들의합2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());
      st = new StringTokenizer(in.readLine());
      int[] input = new int[N];
      for(int i=0;i<N;i++) input[i] = Integer.parseInt(st.nextToken());

      long sum;
      int count = 0;

      for(int first = 0;first<N;first++){
         sum = 0;
         for(int last=first;last<N;last++){
            sum += input[last];
            if(sum==M) count++;
            if(sum>=M) break;
         }
      }

      System.out.println(count);
   }
}

---

3. 결과