[BOJ] 2003. 수들의 합 2 - (Java)

[BOJ] 2003. 수들의 합 2 - (Java)

Problem

제출일 : 2020-03-15

문제 풀이 시간 : 20M

난이도 : ★

---

link : https://www.acmicpc.net/problem/12100

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

Input

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

Output

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

Example

input

4 2
1 1 1 1

output

3

Solution & Inpression

완전탐색? 포인터의 활용..

code 1 : 처음 문제를 풀 때 한번에 더할 개수를 정하고 그 수만큼 더한 모든 경우의 수를 탐색했다.

code 2 : code 1의 최적화 버전으로 양쪽에 포인터를 두어 목표 값보다 작다면 값을 더하고 작으면 값을 빼는 방법으로 굳이 검사하지 않아도 되는 부분을 검사하지 않을 수 있어 속도가 더욱 빠른 코드이다.

Code 1

언어 : JAVA

메모리 : 26960 kb

실행 시간 : 440 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[] data;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        data = new int[N];
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        ans = 0;
        for (int i = 1; i <= N; i++) {
            solve(i);
        }
        System.out.println(ans);
    }

    private static void solve(int size) {
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += data[i];
        }

        for (int i = size; i < N; i++) {
            if (sum == M)
                ans++;
            sum += data[i];
            sum -= data[i - size];
        }
        if (sum == M)
            ans++;
    }
}

Code 2

언어 : JAVA

메모리 : 27320 kb

실행 시간 : 244 ms

import java.util.Scanner;

public class Main {

    static int N, M, ans, sum;
    static int[] data;
    static int s, e;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        data = new int[N + 1];
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }
        s = 0;
        e = 0;

        while (e <= N) {
            if (sum == M)
                ans++;

            if (sum < M)
                sum += data[e++];
            else
                sum -= data[s++];
        }

        System.out.println(ans);

    }

}