[Baekjoon 2003] 수들의 합 2 - JAVA

[Silver IV] 수들의 합 2 - 2003

문제 링크

성능 요약

메모리: 14912 KB, 시간: 148 ms

분류

브루트포스 알고리즘, 누적 합, 두 포인터

문제 설명

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을 넘지 않는 자연수이다.

출력

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

문제 풀이

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

import java.util.StringTokenizer;

public class q2003{

    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 M = 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 start = 0, end = 0, count = 0, sum = 0;

        while (start < N) {
            if (sum > M || end == N) sum -= arr[start ++];
            else sum += arr[end ++];

            if (sum == M) count ++;
        }

        System.out.println(count);    
    }
}

코드 풀이

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

N과 M을 입력받고 입력으로 주어진 숫자들을 저장하는 용도로 사용할 크기가 N인 정수형 배열 arr을 생성한다.

        for (int i = 0; i < N; i ++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0, end = 0, count = 0, sum = 0;

입력으로 주어진 숫자들을 배열 arr에 저장한다.

반복문을 N번 돌면서 StringTokenizer로 입력을 구분하여 배열 arr에 저장합니다.

부분 배열의 시작 인덱스와 끝 인덱스를 나타낼 start와 end를 선언하고, 합이 M인 부분 배열의 개수를 세는 count를 선언해준다.

sum은 현재 부분 배열의 합을 저장하는 변수로 사용한다.

        while (start < N) {
            if (sum > M || end == N) sum -= arr[start ++];
            else sum += arr[end ++];

            if (sum == M) count ++;
        }

        System.out.println(count);

모든 부분 배열을 확인하기 위해 start가 N보다 작은 동안 while 루프를 실행한다.

현재 부분 배열의 합이 M보다 크거나 모든 배열을 확인한 경우, 부분 배열의 시작 인덱스를 한 칸 앞으로 이동시키기 위해 sum이 M보다 크거나 end가 N과 같다면, sum에서 arr[start] 값을 빼고 start를 증가시킨다.

그렇지 않은 경우, 현재 부분 배열의 합이 M보다 작은 경우, 부분 배열의 끝 인덱스를 한 칸 뒤로 이동시키기 위해, sum에 arr[end] 값을 더하고 end를 증가시킨다.

현재 부분 배열의 합이 M과 일치하는 경우 count를 증가시키기 위해, sum이 M과 같다면, count를 증가시킵니다.

모든 부분 배열을 확인한 후, 합이 M인 부분 배열의 개수인 count를 출력한다.