[백준] 1806번 : 부분합

문제

 

 

접근 방식

주어진 수들의 부분 수열의 합이 S 이상인 것 중에 가장 길이가 짧은

부분 수열을 찾아야 하는 문제로 이분 탐색이나 투 포인터를 사용해 풀 수 있는데

투 포인터를 연습 중이기 때문에 투 포인터를 사용해서 풀었다.

 

이전 글에서 풀었던 2230번 문제와 비슷한 문제라 풀기는 쉬웠는데

정렬을 해야 하는줄 알고 하고 풀다가 맞왜틀을 시전하느라 시간을 날렸다.

a = {5 1 3 5 10 7 4 9 2 8}  /  15

sum		a[i]	count
5		5		1
6		1		2
9		3		3
14		5		4
24		10		5		v
19		-5		4		v
18		-1		3		v
15		-3		2		o

 

위와 같이 10개의 수가 주어지고, 부분 수열의 합이 15이상인 경우를 살펴보면

시작 점을 0, 비교할 인덱스는 1부터 시작했을 때, 합이 15 이상이 될 때까지 더하다

15 미만이 될 때까지 넣은 순서대로 값을 다시 빼주고

다시 15 이상이 될 때까지 더해주는 것을 반복하면서

가장 짧은 수열의 길이를 찾아주면 된다.

 

풀이

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());

		st = new StringTokenizer(br.readLine());
		int[] arr = new int[n];

		int x = 0;

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			arr[i] = num;
			x += num;
		}

		if (x < s) {
			System.out.println(0);
			return;
		}

		int end = 1;
		int count = 1;
		int sum = arr[0];
		int min = Integer.MAX_VALUE;


		for (int start = 0; start < n; start++) {
			while (sum < s && end > start && end < n){
				count++;
				sum += arr[end++];
			}

			if (sum >= s) {
				min = Math.min(min, count);
			}

			count--;
			sum -= arr[start];
		}

		System.out.println(min);
	}
}