728x90
반응형
1806번: 부분합
문제
https://www.acmicpc.net/problem/1806
풀이
부분합이 S 이상인 부분합 중 길이가 가장 작은 것의 길이를 구하는 문제다. 시간복잡도가 O(N^2)인 알고리즘으로 풀면 시간 초과를 받는다. 따라서 O(N)인 알고리즘으로 풀어야 한다. 그중 하나가 투 포인터를 사용해서 푸는 방법이다.
left와 right를 모두 0으로 두고 sum = v[0]으로 초기값을 설정한다. 합(sum)은 인덱스가 left부터 right까지 수열의 합이다. 수열의 각 수에 대해 현재까지의 합을 확인한다. 투 포인터를 사용했고 left부터 right까지의 합이므로 left가 right를 넘어가면 안 된다. 또한 right도 전체 수열의 크기인 n을 넘어가면 안 된다.
- 합이 S보다 작으면 right를 1 증가시키고 right 인덱스의 수를 합에 더한다.
- 합이 S와 같으면 수열의 크기가 답보다 작으면 갱신한다. 그리고 right를 1 증가시키고 right 인덱스의 수를 합에 더한다.
- 합이 S보다 크면 수열의 크기가 답보다 작으면 갱신한다. 그리고 left 인덱스의 수를 합에서 빼고 left를 1 증가시킨다.
위 방법대로 전체를 탐색하면 시간복잡도 O(N)으로 답을 구할 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, s;
cin >> n >> s;
vector<int> v(n, 0);
for (int i = 0; i < n; i++)
cin >> v[i];
int left = 0, right = 0, sum = v[0], ans = n + 1;
while (left <= right && right < n)
if (sum < s) {
sum += v[++right];
} else if (sum > s) {
ans = min(ans, right - left + 1);
sum -= v[left++];
} else {
ans = min(ans, right - left + 1);
sum += v[++right];
}
cout << (ans == n + 1 ? 0 : ans);
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 16964 DFS 스페셜 (0) | 2023.03.23 |
---|---|
[백준 / BOJ] C++ 1647 도시 분할 계획 (0) | 2023.03.22 |
[백준 / BOJ] C++ 27498 연애 혁명 (0) | 2023.03.21 |
[백준 / BOJ] C++ 11780 플로이드 2 (0) | 2023.03.21 |
[백준 / BOJ] C++ 5214 환승 (0) | 2023.03.20 |