[BOJ 1806] 부분합 (Java, 투 포인터)

 

 

 

---

문제 링크

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

1806번: 부분합

---

풀이

- 투 포인터 문제 

- 시간 복잡도 O(N) 

- 정답의 최대 길이는 100,000 , 구하려는 S의 최대는 10^9 이므로 Integer로 풀이 가능

---

제출 코드

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

public class Main {
    
    static int N, S;
    static int[] NUMBERS;
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

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

    static void pro() {
        int L = 1, R = 1, ans = 100000;
        int sum = 0;

        while(L <= N) {
            while(R <= N && sum < S) {
                sum += NUMBERS[R];
                R += 1;
            }

            if(sum >= S) {
                ans = Math.min(ans, R - L);
            }

            sum -= NUMBERS[L];
            L += 1;
        }

        if(ans == 100000) ans = 0;

        System.out.println(ans);
    }

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