[G4] 백준 1806번 부분합 C++ 누적 합, 투 포인터

리뷰

 

포인터 두개를 늘려가며 수열에서의 부분합이 특정 수 이상이 되는 가장 짧은 길이를 찾는 문제

https://www.acmicpc.net/problem/1806

 

문제 풀이

1. 수열의 길이 n, 찾을 값 d, 정답 식별용 ans, 수열의 정보 배열lst를 전역 변수로 설정해 준다.
2. n과 d값을 입력받고, n길이의 수열 정보를 lst 배열에 입력받아 준다.
3. 전위 포인터s와 후위 포인터e를 모두 0으로 초기화 해주고 sum을 lst의 0번째 인덱스의 수로 초기화 해준다.
4. s가 e보다 앞서거나 e가 n의 범위를 벗어나기 전까지 while 루프를 진행한다.
5. 현재 sum값이 d보다 작다면 e를 증가시키고 sum에 lst의 e번째 인덱스의 수를 추가해 준다.
6. 만약 반대라면 ans를 e - s + 1과 비교하여 길이의 최소값을 갱신시켜 준다.
7. 이어서 sum에서 lst의 s번째 인덱스의 수를 빼준 뒤 s를 증가키셔준다.
8. 탐색이 완료된 후 ans가 초기값과 동일하다면 0을, 다르다면 ans값 자체를 출력해 주면 된다.

 

참고 사항

처음엔 정렬해서 이분 탐색을 하려 했으나, 수열은 입력받은 상태 그대로 사용해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, d, ans = 1e9;
int lst[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> d;
	for (int i = 0; i < n; i++) cin >> lst[i];
	int s = 0, e = 0, sum = lst[0];
	while (s <= e && e < n) {
		if (sum >= d) {
			ans = min(ans, e - s + 1);
			sum -= lst[s];
			s++;
		}
		else {
			e++;
			sum += lst[e];
		}
	}
	if (ans == 1e9) cout << 0;
	else cout << ans;
}