BOJ 1806. 부분합
랭크 : 골드4
문제 풀이
부분 수열의 시작과 끝을 잡아, 합이 S보다 크다면 시작을, 작다면 끝을 움직이며 부분 수열을 찾습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int N, S;
int main() {
fastio;
cin >> N >> S;
vector<int> arr(N, 0);
int ans = N + 1;
for (int i=0; i < N; i++) {
cin >> arr[i];
}
int start = 0;
int end = 1;
int total = arr[start];
while (1) {
if (total >= S) {
ans = min(ans, end - start);
total -= arr[start];
start++;
} else {
if (end == N) break;
total += arr[end];
end++;
}
}
if (ans == N + 1 ) cout << 0 << endl;
else cout << ans << endl;
}알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| 투 포인터 | $O(N)$ | $O(N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 2473. 세 용액 (0) | 2022.07.09 |
|---|---|
| BOJ 1005. ACM Craft (0) | 2022.07.08 |
| BOJ 9527. 1의 개수 세기 (0) | 2022.07.07 |
| BOJ 2887. 행성 터널 (0) | 2022.07.07 |
| BOJ 1007. 벡터 매칭 (0) | 2022.07.07 |