[Java] 백준 1806번 : 부분합

문제

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

 

접근 방법

1. N개의 수열에서 부분합 중 합이 S가 되는것을 구하는 문제이다.
2. 완탐으로 푼다면 10만 *10만 시간초과가 발생할 것이다.
3. 따라서 투포인터로 풀 수 있었다.

코드

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,S;
    private static int[]arr;
    private static int count = 0;
    private static int min = Integer.MAX_VALUE;

    //입력
    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());
        S = 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 ;
        int sum = 0;

        while(s <= N && e <= N){
            if(sum<S){
                sum+=arr[e];
                e++;
            }else{
                sum-=arr[s];
                s++;
            }

            if(sum>=S){
                min = Math.min(min,e-s);
            }
        }

        if(min == Integer.MAX_VALUE){
            System.out.println(0);
        }else System.out.println(min);
    }


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