[BAE/<JOON> 문제풀이] 1806. 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

투포인터 알고리즘::

 

탐색범위 내의 2개의 포인터*를 잡고 각각의 위치를 조절해가며 탐색하는 기법

 

풀이::

 

문제에서 요구하는 조건은 구간의 합이 주어진 K 이상일 때의 구간의 최소 길이이므로 미리 구간합을 구해두면

 

2개의 인덱스 사이의 합을 상수시간에 구하며 탐색 할 수 있다.

 

두 인덱스 s와 e사이의 합을 구간합으로 구하며 합이 K보다 크다면 s를, 작다면 e를 늘려가며 최소 길이를 구한다.

 

만약 K가 0이라면 수를 더하지 않아도 조건이 충족되므로 0을 출력하고 탐색을 종료한다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	int k;
	cin >> n >> k;
	if (k == 0) {
		cout << 0;
		return 0;
	}
	vector<int> arr(n + 1);
	vector<int> parr(n + 1);
	parr[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		parr[i] = parr[i - 1] + arr[i];
	}
	int s, e;
	s = 1;
	e = 1;
	int mn = 2100000000;
	while (e <= n) {
		int sum = parr[e] - parr[s - 1];
		if (sum >= k) {
			int s1 = e - s + 1;
			mn = mn < s1 ? mn : s1;
			s++;
		}
		else {
			e++;
		}
	}
	if (mn == 2100000000) {
		cout << 0;
		return 0;
	}	
	cout << mn;
	return 0;
}

 

 

 

* C에서 사용하는 메모리 포인터가 아니라 배열내의 인덱스를 저렇게 표현함