ProblemSolving/Two_pointer_sumOfNumber2.cpp at main · shinbian11/ProblemSolving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

// F_I 사용하면 cin 과 scanf 를 섞어서 쓰면 안된다!
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

int main()
{
	F_I;

	//[백준] 1806번 : 부분합 (투 포인터)
	int n, s;
	cin >> n >> s;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];

	int left = 0, right = 0, sum = v[0], ans = 1e9;

	while (left <= right && right < n)
	{
		if (sum < s)
		{
			right += 1;
			if(right<n)
				sum += v[right];
		}
		else if (sum == s)
		{
			if (right - left + 1 < ans) //최소 길이 찾는 부분
				ans = right - left + 1;

			right += 1;
			if (right < n)
				sum += v[right];
		}
		else if (sum > s)
		{
			if (right - left + 1 < ans) //최소 길이 찾는 부분
				ans = right - left + 1;

			sum -= v[left];
			left += 1;
			if (left > right && left < n)
			{
				right = left;
				sum = v[left];
			}
		}
	}

	if (ans == 1e9)
		cout << 0 << '\n';
	else
		cout << ans << '\n';

	return 0;
}