[Algorithm] 1806 - 부분합 (JAVA)

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

1806번: 부분합

---

알고리즘 

부분합의 짧은 길이를 출력하는 문제로 이중 반복문을 사용하면 시간초과가 발생하며, 투포인터를 사용해야하는 문제이다.

start, end를 0으로 초기화한 후, end++를 해가며 sum의 값을 더한다. sum이 S보다 크면 길이를 측정하고, start를 end 전까지로 이동한다.

---

풀이

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

public class Main {
    static int start, end;
    static int N, S;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        start = 0;
        end = 0;
        arr = new int[N+1];
        int answer = Integer.MAX_VALUE;
        int total = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        while (start <= N && end <= N) {
            if (total >= S && answer > end - start) answer = end - start;
            if (total < S) total += arr[end++];
            else total -= arr[start++];
        }
        if (answer == Integer.MAX_VALUE) System.out.println("0");
        else System.out.println(answer);
    }
}