[백준 JAVA]1806 부분합

[문제 링크] 백준 자바 1806 부분합 투포인터 누적합 

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

1806번: 부분합

[생각 흐름]

투 포인터를 활용하여 문제를 해결했다.

먼저 만약 입력 값이 이미 원하는 값 이상이면 최소 길이가 1 임으로 브레이크하고 반환하였다.

 

그 이후에는 먼저 원하는 목푯값보다 클 때까지 right를 오른쪽으로 이동하면 더해간다.

만약 현재 값을 더했을 때 목푯값보다 커진다면 길이를 right-left+1과 ans 중 더 작은 값으로 변환하고, sum에서 현재 값을 빼고

left를 증가시킨다.

위 과정을 반복하다 left가 가능할 때까지 이동하고(if문 안에서 먼저 비교해보고 right를 이동하기 때문에), right가 끝에 도달했을 때 벗어날 수 있도록 하였다.

초기값은 Integer.MAX_VALUE로 두어서 만약 이 값이 유지된다면 불가능하다는 소리로 0으로 바꿔서 출력하도록 하였다.

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine());
        int line = Integer.parseInt(st.nextToken());
        int goal = Integer.parseInt(st.nextToken());

        st= new StringTokenizer(br.readLine());
        int ans =Integer.MAX_VALUE;

        int left =0;
        int right = 0;
        long sum =0;
        int arr[] = new int[line];


        for(int i=0;i<line;i++)arr[i] = Integer.parseInt(st.nextToken());
        while(right<line){
            if(arr[right]>=goal) {
                ans = 1;
                break;
            }
            if(sum + arr[right] >= goal ){
                sum -= arr[left];
                ans = Math.min(right-left+1,ans);
                left++;
            }
            else sum += arr[right++];
        }

        if(ans ==Integer.MAX_VALUE)ans = 0;
        System.out.println(ans);

    }
}