[백준] 1806. 부분합 (Java)

 

문제

1806번: 부분합

 

알고리즘

누적 합(Prefix Sum), 투 포인터

 

풀이

연속된 수들의 부분합을 구하기 때문에 누적 합을 사용하면 빠르게 부분합을 구할 수 있다.

a번째 원소부터 b번째 원소까지의 합 = [b번째까지의 누적합] - [a-1번째까지의 누적합] 이다.

 

sumAtoB = prefixSum[B] - prefixSum[A-1]

 

부분합 중 합이 S가 되는 것을 구하기 위해서 투 포인터를 사용한다.

시작 포인터를 start, 끝 포인터를 end라고 한다면,

현재 부분합 prefixSum[end] - prefixSum[start] 가

S보다 크다면 end 를 1 증가시켜 값을 크게 만들고 최소 길이를 갱신한다.

S보다 작다면 start 를 1 증가시켜 값을 작게 만든다.

 

만약 end가 N보다 커지면 현재 부분합이 S보다 작지만 부분합을 더 크게 만들 방법이 없으므로 진행을 멈춘다.

 

 

코드

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

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[] prefix = new int[N + 1];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; i++) {
			int num = Integer.parseInt(st.nextToken());
			prefix[i] = prefix[i - 1] + num;
		}

		int s = 1;
		int e = 1;
		int min = Integer.MAX_VALUE;

		while (e <= N) {
			if (prefix[e] - prefix[s - 1] >= S) {
				min = Math.min(min, e - s + 1);
				s++;
			} else {
				e++;
			}
		}

		if (min == Integer.MAX_VALUE)
			min = 0;
		System.out.println(min);
	}
}