그럴듯한 개발 블로그
Published 2023. 11. 4. 15:48
백준 1806 부분합 c++ <algorithm>/백준
반응형

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

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

투포인터 문제다. 드러운 예외는 없었다.

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

using namespace	std;

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

	int n, m, res = 2147483647;
	vector<int> v;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		v.push_back(input);
	}
	int start = 0, sum = v[0];
	for (int end = 0; end < v.size(); end++) {
		while (start + 1 <= end && sum - v[start] >= m)
			sum -= v[start++];
		if (sum >= m)
			res = min(res, end - start + 1); // 길이니까 + 1
		sum += v[end + 1];
	}
	if (res == 2147483647)
		cout << '0';
	else
		cout << res;
}
반응형

'<algorithm> > 백준' 카테고리의 다른 글

백준 10844 쉬운 계단 수 c++  (0) 2023.11.20
백준 3184 양 c++  (0) 2023.11.05
백준 2230 수 고르기 c++  (0) 2023.11.04
백준 20310 타노스 c++  (1) 2023.10.24
백준 1911 흙길 보수하기 c++  (1) 2023.10.14
profile

그럴듯한 개발 블로그

@donghyk2

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!