백준 2003 번 : 수들의 합 2 풀이 (Java)

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

Key Point

이 문제를 2중 for문을 이용해 완전 탐색으로 돌리면 시간 초과가 날 것이라 짐작했다. N의 범위가 1에서 10000까지인데, 10000 * 10000 의 연산을 0.5초의 시간 제한에서 할 수 있을리가.

 

이 문제는 투 포인터 알고리즘 문제이다. 투포인터 알고리즘이란,

1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘 이다.

 

구간의 합을 구하는 시작점을 start 로, 끝 점을 end 로 둔다. (start <= end)

그 뒤, 목표하는 값보다 구간합이 작으면 end 위치의 값을 더해주고, end 를 증가시켜주면서 값을 키워간다.

그러다가 구간합이 목표값보다 커지면, 이번에는 기존 start 위치의 값을 빼주고, start 를 증가시켜주며, 범위와 값을 같이 줄여나간다.

 

그 점만 잘 알고나서 보면 쉬운 문제인데, 구현을 좀 잘못하면 저렇게 틀릴 수 있다. 나의 경우는 인덱스 문제였다.

 

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

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N,M;
    static int[] arr;

    static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        arr = new int[N+1];
        StringTokenizer line = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(line.nextToken());
        }
    }

    static void solve() {
        if(N == 1 && arr[0] == M) {
            System.out.println(1);
            return;
        }
        // 1 1
        // 1
        // 의 반례를 잡기 위해서 넣었다.
        int ans = 0, start = 0, end = 0, sum = 0;
        while(end <= N) { // end 가 배열 범위를 초과하면 break해준다.
            if(sum >= M) {
                sum -= arr[start++];
                // 2. 구간합이 목표값 보다 크거나 같으면, sum -= arr[start];
                // start += 1;
            } else if(sum < M) {
                sum += arr[end++]; 
                // 1. 구간합이 목표값 보다 작으면, sum += arr[end];
                // end += 1;
            }
            if(sum == M){
                ans++;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
    }
}