[백준] 1806 부분합

백준 1806 부분합

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

• 부분 합 알고리즘 풀이 (시간 초과)

#include <iostream>
using namespace std;

typedef unsigned long int ul;
const int MAXN = 100000 + 1;

int N;
ul S;
int num[MAXN];
ul psum[MAXN];

void getpsum() {
	psum[0] = num[0];
	for (int i = 1; i < N; ++i)
		psum[i] = psum[i - 1] + num[i];
	return;
}

int getlen() {
	if (psum[N-1] < S) return 0;

	for (int len = 1; len <= N; ++len) {
		//start = 0
		if (psum[len - 1] > S) return len;
		//start = 1 ~
		for (int start = 1; start + len - 1 < N; ++start)
			if (psum[start + len - 1] - psum[start-1] > S)
				return len;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;
	for (int i = 0; i < N; ++i)
		cin >> num[i];

	getpsum();
	cout << getlen();
	return 0;
}

투 포인터 알고리즘 풀이

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

typedef unsigned long int ul;
const int MAXN = 100000 + 1;

int N;
ul S;
int num[MAXN];

int getlen() {
	//base case
	if (S == 0) return 1;

	int minlen = MAXN;
	int start = 0;
	int end = 0;
	ul psum = 0;

	while (end <= N) {
		if (psum >= S) {
			minlen = min(minlen, (end - 1) - start + 1);
			psum -= num[start++];
		}
		else if (psum < S) 
			psum += num[end++];
		
	}

	if (minlen == MAXN) return 0;
	else return minlen;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> S;
	for (int i = 0; i < N; ++i)
		cin >> num[i];

	cout << getlen();
	return 0;
}