[백준 C++] 1806 부분합 - 투포인터

1806번: 부분합

#include <iostream>
#include <algorithm>
using namespace std;

int Sum[100000];

void Init(int N)
{
	int Num;
	cin >> Num;
	Sum[1] = Num;
	for (int i = 2; i <= N; ++i)
	{
		cin >> Num;
		Sum[i] = Sum[i - 1] + Num;
	}
}

int GetLength(int N, int S)
{
	int Min = 100000;

	int Left = 1;
	int Right = 1;
	while (Left <= Right)
	{
		int SubSum = Sum[Right] - Sum[Left - 1];

		if (SubSum >= S)
		{
			int Length = Right - Left + 1;
			if (Length < Min)
			{
				Min = Length;
			}

			++Left;
		}
		else
		{
			++Right;
			if (Right > N)
			{
				break;
			}
		}
	}

	if (Min == 100000)
	{
		return 0;
	}

	return Min;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, S;
	cin >> N >> S;

	Init(N);

	cout << GetLength(N, S);
}

---

 

구간 합과 투 포인터를 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 1번 ~ N번 숫자까지 구간합 배열 저장

2. Left, Right를 1부터 N까지 이동하며 Left번 숫자 ~ Right번 숫자의 구간합 체크

2-a. 해당 구간합이 조건을 만족할 경우, Left를 오른쪽으로 이동하며 더 짧은 길이의 구간합 체크

2-b. 해당 구간합이 조건을 만족하지 않는 경우, Right를 오른쪽으로 이동하며 더 긴 길이의 구간합 체크

2-c. Left가 Right를 넘어간 경우는 조건을 만족하는 구간합의 길이가 1로 가장 짧은 경우로 반복문 탈출

2-d. Right가 N을 넘어간 경우는 더 이상 조건을 만족하는 구간을 찾을 수 없으므로 반복문 탈출