[백준/BOJ] 백준 1806번 : 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

투 포인터(두 포인터) 알고리즘을 이용해 문제를 해결한다.

 

코드

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

int n, s;
vector<int> input_data;

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

	cin >> n >> s;

	for (int i = 0; i < n; i++)
	{
		int input;

		cin >> input;
		input_data.push_back(input);
	}

	int start_point = 0;
	int end_point = 0;
	int sum = 0;
	int result = 987654321;

	//투 포인터
	while (1)
	{
		if (sum >= s)
		{
			result = min(result, end_point - start_point);

			sum -= input_data[start_point];
			start_point++;
		}

		else if (end_point == n)
			break;

		else if (sum < s)
		{
			sum += input_data[end_point];
			end_point++;
		}
	}

	//합을 만드는것이 불가능할때
	if (result == 987654321)
		result = 0;

	cout << result;

	return 0;
}