[백준(Baekjoon)][자바(java)] 1806 : 부분합 / 두 포인터

 

www.acmicpc.net/problem/1806

1806번: 부분합

 

문제 풀이

 

이전 문제 참고 :  hyunjiishailey.tistory.com/261

 

import java.io.*;
import java.util.*;

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()), s = Integer.parseInt(st.nextToken());
		int a[] = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		br.close();

		int left = 0, right = 0, sum = 0, ans = n;
		while (true) {
			if (sum >= s) {
				ans = Math.min(ans, right - left);
				sum -= a[left++];
			} else {
				if (right == n) break;
				sum += a[right++];
			}
		}

		System.out.println(ans == n ? 0 : ans);
	}

}

 

* 두 포인터

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