Baekjoon 1806 부분합 JAVA

1806번: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

풀이

값을 하나씩 입력받으면서 누적된 합이 원하는 값보다 작다면 계속 더하고, 

누적된 값이 크다면 tail pointer를 하나씩 감소하며 값을 뺀다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int f=0,e=0,sum=0,ans=Integer.MAX_VALUE;
		int [] arr = new int[n+1];
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			// 입력받는 모든 값을 투포인터를 이용하여 뒤로 더함
			sum+=arr[e++];
			// 만약 sum이 s보다 크다면
			if(sum>=s) {
				while(sum-arr[f]>=s && f<n)	// 앞에서부터 값을 뺌으로 최소한의 길이를 만듦
					sum-=arr[f++];
			}
			if(sum>=s && e-f<ans) {	// s가 sum보다 크거나 같고, e-f 즉 길이가 답으로 저장된 길이보다 짧으면 대체
				ans=e-f;
			}
		}
		if(s==0)	// 만약에 s가 0이라면 아무런 값이나 하나를 선택하면 되기에 답을 1로 바꿔줌
			ans=1;
		// 처음에 ans를 MAX값을 주어 한번이라도 값이 바뀌지 않는다면 s를 만족하지 않는 합이기에 이때는 0을 출력해줌 
		System.out.println(ans==Integer.MAX_VALUE?0:ans);
			
	}
}