백준[1806] 부분합

아이디어

• [투포인터]를 사용할 줄 안다

접근방식

1. 투포인터를 사용해서 길이를 점차 늘려가며 합한 값이 S 이상이 되는지 검사한다
   -> S 이상이라면, 맨 왼쪽 길이를 줄여도 S 이상일 수도 있기에, 시작 포인터를 1씩 증가시켜준다
   -> S 미만이라면, 아직 값의 개수가 부족하기에, 끝 포인터를 1씩 증가시켜 값의 개수를 증가시킨다
2. 끝 포인터가 범위를 넘어서거나, 시작 포인터가 끝 포인터를 넘어서면 중단시키고 답을 출력시킨다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>

using namespace std;

int main()
{
	int N, S; scanf("%d %d", &N, &S); 
	vector<int> numbers;

	for (int i = 0; i < N; i++)
	{
		int num; scanf("%d", &num);
		numbers.push_back(num);
	}

	//투포인터 사용
	int start = 0; int end = 0;

	int answer = 0;

	//첫번째 값은 미리 넣어둠
	int added_num = numbers[start];

	//start가 end를 넘어서면 잘못된 접근
	while (start <= end)
	{
		int length = end - start + 1;

		//만약 S보다 크면, start를 증가시켜줌
		if (added_num >= S)
		{
			if (answer == 0) answer = length;
			else if (answer > length) answer = length;
			added_num -= numbers[start];
			start++;
		}

		//만약 S보다 작으면, end를 증가시켜줌
		else if (added_num < S)
		{
			end++;
			if (end == N) break;
			added_num += numbers[end];
		}
	}

	printf("%d\n", answer);

	return 0;
}

평가

투포인터를 사용할 줄 안다면 굉장히 쉬운 문제.
정답률이 굉장히 낮아 의문이 들었지만, 투포인터 개념을 몰랐다면 충분히 햇갈릴 수 있는 문제였습니다.

• 배울 것 : 일정한 수열은 [투포인터]를 사용하는 것을 떠올린다