[Java] 백준 2003번 : 수들의 합 2

문제

https://www.acmicpc.net/problem/2003

 

접근 방법

1. 만약 완전탐색으로 구할 경우 O(N^2) 시간 초과가 발생한다.
2. 따라서 N^2을 O(N) 으로 줄일 수 있는 투 포인터를 생각하여 문제를 구했다.
3. s, e 둘다 0으로 시작하고, 값이 작으면 e를 증가, 값을 초과하면 s를 증가시켰다. 코드를 보는것이 더 이해하기 쉬울 것이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,M;
    private static int[]arr;
    private static int total = 0;
    private static int count = 0;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

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

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

    //실행
    public static void process() {
        int s = 0;
        int e = 0;

        total = arr[0];
        
        
        //while() 안에 조건은 어떤 수 하나가 total 값을 초과할수도 있기 때문에 s와 e
        //어떤 것이 마지막에 도착할지 모른다. 그래서 s<N && e<N 으로 했지만
        //e<N으로 해도 상관없다. 왜냐하면 결국 s를 기준으로 값이 더해지기 때문에
        while(s<N && e<N){
            if(total < M){
                e++;
                total +=arr[e];
            }else if(total > M){
                //값을 빼고 s를 증가시켜야 한다. 순서 주의
                total -=arr[s];
                s++;
            }else{
                count++;
                total -=arr[s];
                s++;
                e++;
                total +=arr[e];
            }
        }

        System.out.println(count);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}