반응형
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 |