🧓2003번. 수들의 합2., 투포인터, 필독!

알고리즘 분류

: 투포인터

경고!

• 예외처리를 하나하나 생각해나가면서 하면 쉽게 풀 수 있음.

• start 가 end보다 앞서게 된다면. end를 동일하게 만들어야 함.
  어떤 경우냐면
  
• 여기에서 4 2 5 부분 중 5가 7이라고 한다면, start가 end보다 뒤로 갈수 있다.
  이렇게 되면 와일문 끝남.

특징

• 1. start 와 end 값이 동일한 곳을 가리킬 수 있음.
     이때, end만 증가시키자.
     순환문 돌면서 start 증가 처리를 하기 때문에

풀이전략

• 반드시 , end 인덱스를 앞에서 부터 시작 해야 함.
• 합 계산하려는 인덱스의 수가 많아질수록, 논리적으로 합이 커짐.

주의할점.

• 1. 각 조건마다, start와 end 인덱스 값이 증가하는데, 내가 만든 컨테이너의
     사이즈를 벗어날 수 있음. 이에 대한 조건 처리를 해야함.
• 2. start가 end보다 값이 커지는 경우가 있음.
     어떠한 경우냐? 합을 구하는 가운데 위치에서 원소 하나를 가지고 타겟값과 비교를 했는데,
     타겟값보다 클 경우, 여기서 아무조건 없다면, 와일문에서 끝나므로.
     계속 진행해서, 경우의 수를 카운팅해줘야함.
     end도 start와 동일하게 만들어야 함.
• 3. 위의 특징으로 인해서 while문에 start <= end // 등호도 포함되어야 함.

연습_1. 브루트포스 참고

코드

#include <iostream>

using namespace std;

#include <vector>
#include <algorithm>

// 2003번. 수들의 합2
// 15:51 ~ 16:37

int main(void)
{
	int n, m;
	cin >> n >> m;

	vector<int>v(n);

	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}

	int start = 0;
	int end = 0;
	int sum = v[start];

	int res = 0;

	while (start <= end && end < v.size())
	{	
		if (sum < m)
		{
			++end;
			if (end >= n)
				break;
			sum += v[end];
		}
		else if (sum == m)
		{
			++res;						
			++end;
			if (end >= n)
				break;
			sum += v[end];

		}
		else if (sum > m)
		{
			sum -= v[start];
			++start;

			// start에 대한 조건을 처리해야 함.		
			// 이런 생각을 할 수 있음. 
			// 가운데에서 start와 end가 동일한데, 
			// start를 증가할 경우. 
			// 그러니까 입력 2번에 해당함.
			// 뒷부분의 인덱스도 진행을 해야함.

			if (start > end)
			{
				end = start;
				sum = v[start];
			}

		}

	}

	cout << res;

}