BOJ 1806 - 부분합

1806번: 부분합 (acmicpc.net)

1806번: 부분합

접근 방법

연속된 수들 중 합이 S 이상인 것들의 길이가 최소인 것을 구하는 문제이다.

전형적인 투포인터 유형의 문제로 쉽게 해결 할 수 있다.

 

문제에서 주의할 점이 S이상 이기 때문에 이 또한 고려해야 한다.

또한, 수의 범위가 꽤 크기 때문에 자료형 선정 시도 고려해야 한다.

 

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

#define MAX 100001
#define ll long long

vector<ll> arr;
ll n, s;
ll res = MAX + 1;

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

	for (int i = 0; i < n; i++) {
		ll tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

	ll l = 0;
	ll r = 0;
	ll tmp = 0;
	for (l = 0; l < n; l++) {
		
		
		while (r < n && tmp < s) {
			tmp += arr[r];
			r++;
		}
		if (tmp >= s) {
			res = min(res, (r - l));
		}

		tmp -= arr[l];
	}
	if (res == MAX + 1)
		cout << 0;
	else
		cout << res;
}