[백준] 1806 부분합 문제풀이 C++ :: 투 포인터 :: DANIDANI

1806 부분합

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

기본적인 투 포인터 알고리즘 문제! (시간복잡도 O(N))

문제 딱 보고 이중 for문으로 풀면 시간초과 날 수 있다. (시간복잡도 O(N^2))

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, s;
	cin >> n >> s;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)	// 배열 입력
		cin >> arr[i];
	
	int start = 0, end = 0, sum = 0, minLen = 0x7FFFFFF;
	while (start <= end) {
		if (sum >= s) {	// 현재 포인터의 합이 s보다 크거나 같으면 start ++
			minLen = min(minLen,end - start);	// 가장 짧은 길이만 저장
			sum -= arr[start++];
		}
		else if (end == n) break;
		else sum += arr[end++];	// end++ 함으로써 sum 증가
	}

	if (minLen == 0x7FFFFFF) cout << 0 << endl;	// 불가능 하면 0 출력
	else cout << minLen << endl;
	return 0;
}

 

---

https://danidani-de.tistory.com/2

투 포인터 알고리즘에 대해 더 알고 싶으면

투 포인터 알고리즘(Two Pointers Algorithm) :: DANIDANI