[백준/C++] 1806번 부분합 /투 포인터/two_pointer - (1)

백준 1806번 부분합

 

1806번 부분합 풀이

 

이 문제 역시 투 포인터 알고리즘으로 풀어야 시간 초과가 뜨지 않는다.

밑에 투 포인터 알고리즘과 그 문제에 대해 적어놓은 것이니 참고하길 바란다.

 

[백준/C++] 2559번 수열 /투 포인터 알고리즘/ two_pointer - (1)

 

 

이 문제는 S라는 부분합의 기준 값을 줌으로써 부분합이 S를 넘겨야되며, 이 중 길이가 가장 짧은 것을 출력해야한다.

 

부분합 투 포인터 정답 코드

	int len = 100001;
	int st = 0;
	int en = 0;
	int result = 0;
	int che_len = 0;
	while (en < n) {
		if (result >= s) {
			if (che_len < len) len = che_len;
			result -= vec[st];
			che_len--;
			st++;
		}
		else {
			result += vec[en];
			en++; che_len++;
		}
	}

 

부분합 풀이를 보면, 시간 복잡도 O(n)으로 해결한 것을 볼 수 있다.

 

result 값을 매번 새로 하는 것이 아니라, result 값을 유지하면서 st(start) , en(end) 지점을 새로 갱신하면서 이어나가면 시간복잡도를 확 낮출 수 있다. 

 

result값이 s보다 작으면 en ++ 해줘서 result += vec[en]값을 추가해준다. 만약, result 값이 s보다 크다면 result -= vec[st] 를 해주고, st++해준다.

 

부분합 이중 for문 코드 

	for (int i = 0; i < n; i++) {
		long long result = 0;
		int che_len = 0;
		for (int j = i; j < n; j++) {
			result += vec[j];
			che_len++;
			
			if (result >= s) {
				if (che_len < len) len = che_len;
				break;
			}
			if (che_len >= len) break;
		}
	}

 

위 코드는 시간복잡도 O(n^2)의 풀이이다. 중간 조건을 할당해서 이중 for문이라도 중간에 빠져나오게 하면 될줄 알았지만, 0.5초란 시간은 너무 가혹했다...ㅋㅋ

 

 

#include<iostream>
#include<vector>
using namespace std;

vector<int> vec;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

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

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		vec.push_back(num);
	}

	int len = 100001;
	int st = 0;
	int en = 0;
	int result = 0;
	int che_len = 0;
	while (en < n) {
		if (result >= s) {
			if (che_len < len) len = che_len;
			result -= vec[st];
			che_len--;
			st++;
		}
		else {
			result += vec[en];
			en++; che_len++;
		}
	}


	if (len == 100001) {
		cout << 0;
		return 0;
	}
	cout << len;
}