[백준 C++] 1806번 : 부분합

1. 문제

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

1806번: 부분합

 

2. 알고리즘 분류

• 누적 합
• 두 포인터

 

3. 소스 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 987654321

using namespace std;

int main()
{
	// N : 수열의 갯수, S : 최소 누적합 입력
	int N, S;
	vector<int> sequence;

	scanf("%d %d", &N, &S);

	// 수열 입력
	for (int i = 0; i < N; i++)
	{
		int num;
		scanf("%d", &num);
		sequence.push_back(num);
	}

	int start = 0;
	int end = 0;
	int sum = sequence[0];
	int min_size = INF;

	// 투 포인터를 통해 index 0 ~ N - 1까지 탐색
	while (start <= end && end < N)
	{
		if (sum < S) // 부분합이 S보다 작으면, 끝 인덱스를 한칸씩 이동
			sum += sequence[++end];
		else  // 부분합이 S보다 크면, 최소의 길이 갱신한 후 시작 인덱스를 한칸씩 이동  
		{
			min_size = min(min_size, end - start + 1);
			sum -= sequence[start++];
		}
	}

	// 만약 최소의 길이가 갱신이 되지 않았다면 0으로 반환
	int ret = 0;
	if (min_size != INF) ret = min_size;

	printf("%d", ret);

	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) 투 포인터

• 어떤 리스트에 순차적으로 접근해야 할 때, 2개의 점의 위치를 기록하면서 처리하는 알고리즘

int start = 0;
int end = 0;
int sum = sequence[0];
int min_size = INF;

// 투 포인터를 통해 index 0 ~ N - 1까지 탐색
while (start <= end && end < N)
{
	if (sum < S) // 부분합이 S보다 작으면, 끝 인덱스를 한칸씩 이동
		sum += sequence[++end];
	else  // 부분합이 S보다 크면, 최소의 길이 갱신한 후 시작 인덱스를 한칸씩 이동  
	{
		min_size = min(min_size, end - start + 1);
		sum -= sequence[start++];
	}
}