1806 부분합

 

1806번: 부분합

 

배열의 연속된 부분합 중, 합이 S 이상이 되는 가장 짧은 부분의 길이를 구하는 문제이다.

일단 분류는 투 포인터로 되어있는데 난 그냥 이진 탐색 써서 풀었다.

 

먼저 각 구간의 누적합을 계산한 다음, 배열의 첫번째 위치부터 n - 1번째 위치를 구간의 시작점으로 두고,

구간의 끝점은 이진 탐색으로 찾았는데, 끝점이 될 수 있는 left bound는 lbound, right bound는 rbound로 정하고

lbound와 rbound 사이의 거리를 좁혀가는 식으로 이진 탐색을 수행했다. 

 

일단 나는 그냥 문제 풀때 이진 탐색이 생각나서 이렇게 풀기는 했는데,

솔직히 그냥 투 포인터로 푸는게 코드도 간결하고 조금 더 빠르니 이 코드는 참고만 하는 게 좋을 것 같다.

 

 

PS는 양치기가 기본으로 되어야 제대로 된 방식으로 빠르게 문제 풀 수 있을 텐데 갈 길이 멀기만 하다 ㅜㅜ

 

C++

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n, s;
	cin >> n >> s;

	vector<int> vec(n);
	vector<int> sum(n + 1);

	sum[0] = 0;
	for (int i = 0; i < n; ++i) {
		cin >> vec[i];
		sum[i + 1] = sum[i] + vec[i];
	}
	
	if (sum[n] < s)
		cout << 0;
	else {
		int res = n;
		for (int i = 0; i <= n && sum[n] - sum[i] >= s; ++i) {
			int lbound = i, rbound = n, mid;
			while (rbound >= lbound) {
				mid = (rbound - lbound) / 2 + lbound;
				if (sum[mid] - sum[i] == s) {
					if (mid - i < res)
						res = mid - i;
					break;
				}
				else if (sum[mid] - sum[i] > s) {
					if (mid - i < res)
						res = mid - i;
					rbound = mid - 1;
					continue;
				}
				lbound = mid + 1;
			}
		}
		cout << res;
	}
	return 0;
}