1806번 : 부분합 [Java]

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

1806번: 부분합

 

해결방안 

모든 값을 배열에 넣은 뒤 투포인터를 사용해 S이상이 되는 경우를 찾고, 그중 최솟값을 기억한다.

 

주의할 점

처음에 투포인터를 사용하지 않고 for문을 두 개 사용했더니 (for (int i = 0; i < N; i++) /  for (int j = i; j < N; j++)) 시간 초과가 났다. 제발 범위 확인 좀 하자,,

 

전체 코드

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 input = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(input.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		int[] arr = new int[N];
		st = new StringTokenizer(input.readLine(), " ");
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());

		int ans = 987654321;
		int start = 0;
		int end = 0;
		int sum = 0;

		while (true) {

			if (sum >= S) {
				sum -= arr[start];
				start++;
				ans = Math.min(ans, end - start + 1);
			} else if (end == N) // 끝까지 다 봤다.
				break;
			else {
				sum += arr[end];
				end++;
			}
		}
		System.out.println(ans != 987654321 ? ans : 0);
	}
}