백준 Silver 4 수들의 합 2

수들의 합 2 (백준 Silver 4)

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

투 포인터 + 누적합의 문제로
누적합을 통하여
수열의 값을 요소의 총합으로 저장한 후(sums),
이후 j~i 까지의 합을 구할 때
그 차이를 빼줌으로서(sums[i] - sums[j])
빠르게 합을 구하며
수열 내의 ‘합’이 특정한 값 M 인 경우의 수를 구하는 방식이다

‘투 포인터’를 이용하여
인덱스 i와 j를 적절히 이동시켜 값을 구한다

nowSum = sums[i] - sums[j];
라 한다면 그 합이
m이라면 정답 카운트를 + 1
m보다 작다면 i를 올려 총 합을 크게
m보다 크다면 j를 올려 총 합을 작게
만드는 방식이다

처음 제출한 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	vector<int> ip;
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;
		ip.push_back(t);
	}

	int answer = 0;
	vector<int> sums(n,0);
	sums[0] = ip[0];
	for (int i = 1; i < n; i++)
	{
		sums[i] = sums[i - 1] + ip[i];
		if (sums[i] == m)
		{
			answer++;
		}
	}

	int i = 1, j = 0;
	
	while (i < n)
	{
		int nowSum = sums[i] - sums[j];

		if (nowSum == m)
		{
			answer++;
			i++;
			j++;
		}
		else if (nowSum > m)
		{
			j++;
		}
		else
		{
			i++;
		}

	}

	cout << answer;
}

무엇을 고려하지 못하였을까?

1. 일단 누적합을 다소 잘못 구하였다
   Sums[i] -Sums[i-1] 처럼 값 차이가 1이 나오는 경우
   i번째 요소값을 return 해야 하는데
   그 부분을 고려하지 못했다
   따라서 sums를 n+1로 잡은 후
   sums[0] 을 0으로 잡는 방식으로 바꾸었다
   

2. i가 n에 도달하면 j가 어디있든 반복문이 종료한다
   i가 n에 도달하더라도 j가 n까지 올라오며
   합의 값이 m일 수 있는 경우의 수를 포함하지 못한다
   따라서 반복문의 종료 조건을 수정하였고
   i가 이미 최대치라면 대신 j를 올리는 방식으로 수정하였다
   

---

최종 제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	vector<int> ip;
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;
		ip.push_back(t);
	}

	int answer = 0;
	vector<int> sums(n + 1, 0);
	sums[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		sums[i] = sums[i - 1] + ip[i-1];
	}

	int i = 1, j = 0;

	while (true)
	{
		int nowSum = sums[i] - sums[j];

		bool bOveri = false;

		if (i >= n)
			bOveri = true;


		if (nowSum == m)
		{
			answer++;

			if (bOveri == false)
				i++;
			else
				j++;
		}
		else if (nowSum > m)
		{
			j++;
		}
		else
		{
			if (bOveri == false)
				i++;
			else
				j++;
		}

		if (i >= n && j >= n)
			break;
	}

	cout << answer;
}