백준 1806: 부분합(java)

문제

---

풀이

 

투 포인터 기법을 사용하여 다른 부분합 문제들과 동일하게 풀이하되, 합이 S 이상인 연속된 부분합 중 "가장 짧은 것"을 구해야 한다는 점에만 주의하면 된다.

arr[left]부터 arr[right]까지의 누적 합 sum이 S보다 커질 때까지 right 포인터를 한 칸씩 이동하며 sum을 증가시키고, 가장 짧은 부분 합을 구해야 하므로 sum이 S보다 처음 커진 이후로는 left 포인터를 한 칸씩 이동하며 sum>S 이도록 하는 최대의 left를 구한다.

 

전체 코드

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 N=Integer.parseInt(st.nextToken());
		int S=Integer.parseInt(st.nextToken());
		
		int[] arr=new int[N];
		
		st=new StringTokenizer(br.readLine());
		
		for(int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		int left=0, right=0, sum=0;
		int min=Integer.MAX_VALUE;
		
		while(right<N) {
			sum+=arr[right++];
			
			while(sum>=S) {
				min=Math.min(right-left, min);
				sum-=arr[left++];
			}
		}
		
		if(min==Integer.MAX_VALUE) {
			System.out.println(0);
		}
		else {
			System.out.println(min);
		}
	}
}