[ Baekjoon ][JAVA][1806] 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

문제

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

입력

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

출력

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

예제 입력

예제 출력

접근

부분 합을 구하는문제로 정확히 S가 아니라 S이상이지만,
투포인터 알고리즘은 현재 부분합이 S이상이면 가능한 한 구간 크기를 작게 만들기 때문에 투포인터알고리즘으로 간단하게 풀린다!

코드

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

public class SectionSum_1806 {
	static int[] arr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		long S = Integer.parseInt(st.nextToken());
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int result = 100001, sum = 0, lo = 0, hi = 0;
		while(true) {
			if(sum >= S) {
				sum -= arr[lo++];
				result = Math.min(result, hi-lo+1);
			}
			else if(hi == N) break;
			else {
				sum += arr[hi++];
			}
		}
		if(result == 100001) {
			bw.write(0+"\n");
		}else {
			bw.write(result+"\n");
		}
		
		bw.flush();
		br.close();
		bw.close();
	}
}