[백준][2003] 수들의 합2

수들의 합

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초

128 MB

12715

6224

4272

51.015%

문제

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

출력

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

예제 입력

4 2 1 1 1 1

예제 출력

3

예제 입력

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

예제 출력

3

코드

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class bj2003 {

    public static int N, M;
    public static int arr[];

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        System.setIn(new FileInputStream("C://sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = 1;
        for(int tc=1; tc<=T; tc++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            arr = new int[N];

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


            int s = 0;
            int e = 0;
            int sum = 0;
            int cnt = 0;
            while(true) {

                if(s == N) {
                    if(M == sum) {
                        cnt++;
                    }
                    break;
                }

                if(M > sum) {
                    if(sum + arr[s] > M) {
                        sum -= arr[e];
                        e++;
                    }else {
                        sum += arr[s];
                        s++;
                    }
                }else if(M == sum) {
                    cnt++;
                    sum -= arr[e];
                    e++;
                }else {
                    sum -= arr[e];
                    e++;
                }                

            }

            bw.flush();
            bw.write(cnt + "\n");


        }
        bw.close();

    }

}

풀이

투 포인터 알고리즘으로 풀이 가능하다. (유사품 : 슬라이딩 윈도우)

1. left 인덱스, right 인덱스를 정의한다. 코드에서는 left를 e로, right를 s로 명명하였다. (변수명이 좀 별로다. left,right가 더 직관적인 것 같다.)
2. 처음에 left, right는 0이며, 항상 left<=right를 만족한다.
3. 아래의 과정을 right < N 조건하에 반복한다. -> right >= N 이더라도 left를 끝까지 이동시켜본 후 끝내도 된다. 하지만 불필요한 연산이다.
4. sum이 M(구하고자 하는 합) 보다 크면, sum에서 left 위치의 값을 빼고, left를 +1한다.
5. sum이 M보다 작으면, sum에서 right 위치의 값을 더하고, right를 +1 한다.
6. sum이 M과 같으면, 구간합을 하나 찾았으므로, 카운터를 하나 올리고, left를 +1한다.

궁금한점

• 풀이의 3번에서 right가 N에 도달했을때 바로 끝내도 답이 나오는 이유
  반대로 생각해서 right가 N에 도달했고, 앞으로 left가 오른쪽으로 이동할 일만 남았는데, left가 오른쪽으로 이동하면서 새로운 답을 발견할 가능성이 있을까? -> right가 N에 도달한거 자체가 아직 sum이 M보다 작다는 의미이므로, left를 오른쪽으로 마저 이동하면서 sum에서 빼봤자 M에 도달할 수 없다.

• 풀이의 6번에서 right를 +1하는게 아니라, left를 +1하는 이유
  글쎄. 어느걸 올려도 상관없지 않을까? -> 확인필요