Boj 1806) 부분합

문제

백준 1806

큐

시간 복잡도

O(\(\mathrm{N}\))

코드

using ll = long long;

int main()
{
	int n, S; cin >> n >> S;
	queue<int> q; ll sum = 0; int ans = 1e9;
	for (int i = 0; i < n; i++)
	{
		int tmp; cin >> tmp; 
		q.emplace(tmp); sum += tmp;
		while (1)
		{
			if(sum >= S) ans = min<int>(ans, q.size());
			if (q.empty() || sum - q.front() < S) break;
			sum -= q.front(); q.pop();
		}
	}

	if (ans == 1e9) ans = 0;
	cout << ans;
}

투포인터

시간 복잡도

O(\(\mathrm{N}\))

코드

using ll = long long;
ll arr[100001];

int main()
{
	int n, S; cin >> n >> S;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) arr[i + 1] += arr[i];

	int s = 0, e = 0;
	int ans = 1e9;
	while (s <= e && e <= n)
	{
		ll cur = arr[e] - arr[s];
		if (cur < S) e++;
		else if (cur == S) { ans = min(ans, e - s); e++; }
		else { ans = min(ans, e - s); s++; }
	}
	if (ans == 1e9) ans = 0;
	cout << ans;
}

이분탐색

설명

lower_bound() 가 특정 수 이상인 가장 작은 위치를 들고온다. 문제에서 필요한 것은 특정 수 이하의 가장 큰 위치이므로 약간 조정할 필요가 있다. 이게 헷갈려서 조금 헤멨다.

시간 복잡도

O(\(\mathrm{N} \log{\mathrm{N}}\))

코드

using ll = long long;
ll arr[100001];

int main()
{
	int n, s; cin >> n >> s;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int i = 0; i < n; i++) arr[i + 1] += arr[i];

	auto k = lower_bound(arr, arr + 10, arr[10] - s);
	int ans = 1e9;
	for (int i = 1; i <= n; i++)
	{
		ll* j = lower_bound(arr, arr + i, arr[i] - s);
		while (*j > arr[i] - s && j - arr > 0) j--;
		if (*j <= arr[i] - s)
		{
			ans = min(ans, (int)(arr + i - j));
			int k = 0;
		}
	}
	if (ans == 1e9) ans = 0;
	cout << ans;
}