백준(BOJ) 1806번 부분합

문제 : https://www.acmicpc.net/problem/1806

1806번: 부분합

풀이 :

완전 탐색을 이용 시 n이 크기에 시간 내에 처리하지 못하고 투 포인터를 이용해서 처리해보자

 

lo와 hi는 인덱스를 가리키고 0으로 초기화한 후 조건이 만족할 때마다 값을 경신해준다.

 

lo와 hi이 최대로 수행되더라도 2O(n) 이기 때문에 시간 내에 충분히 가능하다.

 

코드 ( C++ )

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int n, s;
	const int INF = 987654321;
	int main()
	{
	cin >> n >> s;
	vector<int> A(n);
	for (auto& i : A)
	cin >> i;
	int sum = 0;
	int lo = 0, hi = 0;
	int ans = INF;
	while (lo < n) {
	if (sum < s && hi < n)
	sum += A[hi++];
	else
	sum -= A[lo++];
	if (sum >= s)
	ans = min(ans, hi - lo);
	}
	if (ans == INF)
	cout << 0 << "\n";
	else
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub