문제 URL : www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
문제 접근법 : 투포인터를 이용한 알고리즘문제인데
배열 v에 입력된수를 차례로 sum이라는 변수에 더해준후 S이상이 되는 지 확인합니다.
S이상이되면 더 더길이가 더길어지기때문에 더 탐색할 필요없이 앞에서 더했던것을 하나하나씩 제거하면서 S보다 작아지면 다시 다음위치부터 sum에 값을 더해주면서 S이상이되는지 반복해서 탐색하면 됩니다.
|
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
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
long long n, s;
vector<long long> v;
int minlen = 1e+9;
void input() {
cin >> n >> s;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
}
void solve() {
long long sum = 0;
int j = 0;
for (int i = 0; i < n; i++) {
int len = i - j + 1;
sum += v[i];
while (sum >= s) {
minlen=min(minlen, len);
sum -= v[j++];
len = i - j + 1;
}
}
cout << (minlen==1e+9?0:minlen) << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs
|
지적할 점이 있거나 궁금한점 혹은 모르는점 혹은 다른아이디어 언제든
댓글은 환영입니다.
'백준' 카테고리의 다른 글
| 백준 16235 나무 재테크 (0) | 2021.02.15 |
|---|---|
| 백준 16920 확장 게임 (0) | 2021.02.15 |
| 백준 20057 마법사 상어와 토네이도 (0) | 2021.02.10 |
| 백준 3190 뱀 (0) | 2021.02.10 |
| 백준 1525 퍼즐 (0) | 2021.01.01 |
