[BOJ] 2003번 : 수들의 합 2

ErroredPasta·2022년 5월 7일
0

BOJ

목록 보기
16/21

문제

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

- 시간 제한 : 0.5초
- 메모리 제한 : 128MB

입력

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

출력

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

접근 방법

코드

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

public class Main {

    static int result = 0;
    static int n, m;
    static int[] numbers;

    public static void main(String[] args) {
        input();
        func();
        System.out.println(result);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        numbers = new int[n];

        for (int i = 0; i < n; ++i) {
            numbers[i] = sc.nextInt();
        }

        sc.close();
    }

    static void func() {
        int left = 0;
        int right = 1;
        int sum = numbers[0];

        for (;;) {
        	// 합이 m보다 작을 경우
            if (sum < m) {
            	// 더 이상 가능한 경우가 없으므로 return
                if (right == n) return;
                
                // 배열의 원소 하나를 추가 시킨다.
                sum += numbers[right++];
            
            // 합이 m보다 크거나 같을 경우
            } else {
            	// m과 같으면 result를 증가
                if (sum == m) ++result;
                
                // 배열의 원소 하나를 제외 시킨다.
                sum -= numbers[left++];
            }
        }
    }
}
profile
Hola, Mundo

0개의 댓글