Baekjoon 1806 부분합

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

결과 2380 KB / 8 ms

언어 C++ 17

 

풀이

투포인터 + 길이 개념 문제

투포인터 개념을 안다면 크게 어려운 문제는 안되는 거 같다.

연속이라는 전제 조건이 붙는 순간 투포인터가 가능하다 라고 알려주는 문제 같다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 100000;

int inputs[MAX];

int _min(const int a, const int b) { return b ^ ((a ^ b) & -(a < b)); }

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

	int res = 0;
	int n, m; cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> inputs[i];

	int left = 0, right = 0;
	int sum = 0;
	while (right <= n) {
		if (sum < m)
			sum += inputs[right++];
		else
		{
			if (res)
				res = _min(right - left, res);
			else
				res = right - left;

			sum -= inputs[left++];
		}
	}

	cout << res;


	return 0;
}