1806 부분합

처음엔 N^2으로 탐색을 시도했는데, 시간 초과가 나서 다시 생각해보니 worst case가 10^10인걸 알았다.

그리고 탐색의 범위를 줄일 수 있는 방식으로 이분탐색을 생각했지만 구현 방법이 까다로워 고민했는데, 다른 사람의 코드를 참고해보니 투포인터란 개념으로 범위를 줄일 수 있다는걸 알게 되었다.

 

투포인터란, 일정 범위의 값들을 해로 갖는 문제를 효율적으로 풀기 위한 개념이다.

문제의 정답 코드를 보며 예시를 들어보겠다.

처음 반복문은 이분탐색과 유사하다. 그런데, 오른쪽 포인터가 탐색 범위를 벗어나지 않는 조건이 포함된걸 알 수 있다.

이 문제에 적용한 개념은 다음과 같다.

1. 문제의 조건을 만족하면, 정답을 갱신하고 탐색 범위를 늘린다. (++right)

2. 문제의 조건에 미달하면, 탐색 범위를 늘린다. (++right)

3. 문제의 조건을 초과하면, 탐색 범위를 좁힌다. (left++)

 

1번의 이유는 더 좋은 해를 찾기 위해 범위를 늘리는 것이고, 2번은 문제의 정답을 구하기 위해서 필요한 과정이며, 3번은 1번의 이유와 같다.

 

고찰

개인적으로 모르면 틀리는 문제라고 생각했다. 탐색 범위를 줄이기 위해 이분 탐색까지 생각했지만, 구현이 어려워서 그 이상으로 넘어가지 못한 문제다.

 

정답코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_SIZE 100000
#define INF 987654321
int N, S;
int arr[MAX_SIZE];
int dp[MAX_SIZE];
int result = INF;
void Search()
{
	int left = 0, right = 0;
	long long sum = arr[0];
	while (left <= right && right < N) {
		//조건을 만족하지 않으면, 탐색 범위를 늘린다.
		if (sum < S)
			sum += arr[++right];
		//조건을 일치하면, 정답을 갱신하고 탐색 범위를 늘린다.
		else if (sum == S) {
			result = min(result, (right - left) + 1);
			sum += arr[++right];
		}
		//조건을 초과하면, 탐색범위를 줄인다.
		else {
			result = min(result, (right - left) + 1);
			sum -= arr[left++];
		}
	}
	if (result == INF)
		printf("0\n");
	else
		printf("%d\n", result);
}
int main()
{
	scanf("%d %d", &N, &S);
	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);
	Search();
	return 0;
}