[백준] C++ 부분합(1806)

누적합, 투포인터 문제이다.

 

문제풀이방법

start와 end 포인터를 둬서 하나씩 이동시키면서 문제를 풀어야 한다.

start와 end를 -1로 초기화했다고 치자.

sum은 0이기 때문에 end를 오른쪽으로 한 칸 이동 키면서 sum+=arr[end]를 해준다.

구하고자 하는 값보다 sum이 작으면 end를 ++해주고 구하고자 하는 값보다 크면 start를 ++해줘서 sum-=arr[start]해준다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;

int main(void)
{
	int N = 0;
	int S = 0;
	int start = -1;
	int end = -1;

	cin >> N >> S;

	for (int i = 0; i < N; i++)
	{
		int num = 0;
		cin >> num;
		v.push_back(num);
	}

	int len = 0;
	int sum = 0;
	int min = 987654321;

	while(true)
	{
		if (sum < S)
		{
			end += 1;
			if (end >= N)//만약 배열의 끝 범위를 넘어가면 멈춘다.
			{
				break;
			}
			len++;
			sum += v[end];
		}
		else
		{
			if (min > len)
			{
				min = len;
			}
			start += 1;
			len--;
			sum -= v[start];
		}

		if (start == end)//start와 end가 같아지면 가장 짧은거로 간주. 
		{
			min = 1;
			break;
		}
	}

	if (min == 987654321)
	{
		cout << 0;
	}
	else
	{
		cout << min;
	}
	
	return 0;
}

만약 start와 end가 같아지게 되면 그 값 하나만으로도 조건이 충족되기 때문에 min을 1로 만들고 break 한다.

min값이 아직 max값이면 어떠한 경우의 수도 조건을 충족하지 못하기 때문에 0을 출력한다.