[백준 1806] 부분합(Java)

문제 링크 : https://www.acmicpc.net/problem/1806

이 문제는 투 포인터를 이용하여 풀 수 있습니다. 연속된 수의 부분합 중 가장 짧은 길이를 구하는 문제이기 때문에 입력 배열을 정렬하지 않으며 탐색합니다. 부분합 중 가장 짧은 길이는 시작 인덱스와 끝 인덱스의 차에 1을 더한 값과 같기 때문에 합이 S보다 크거나 같을 경우 길이값의 최솟값을 갱신하고 투 포인터로 탐색을 진행합니다.

다음은 코드입니다.

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

class Main{
    static int N;
    static long S;
    static int[] A;
    static int res = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) A[i] = Integer.parseInt(st.nextToken());
        getSum(0,0,A[0]);
        if(res == Integer.MAX_VALUE) System.out.println(0);
        else System.out.println(res);
    }

    static void getSum(int s, int e, long sum){
        if(e >= N || s >= N) return;

        if(sum >= S){
            res = Math.min(res, e-s+1);
            getSum(s+1,e,sum-A[s]);
        }
        else{
            if(e+1<N) getSum(s,e+1,sum+A[e+1]);
        }
    }
}