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

투 포인터 문제.

바로 이전에 풀었던 2230번 수 고르기 문제와 비슷한 유형의 문제이다.

정렬하지 않고 푸는 투 포인터 문제이다.

 

문제풀이

연속된 수들의 합 중에서 길이가 가장 짧은 것을 구하면 된다.

나같은 경우에는, front, tail(lo, hi)를 둘 다 0으로 초기화 시켜놓고 front부터 tail까지에 속하는 모든 원소의 합을 통해서 조건을 만들었다.

• 반복문은 front <= tail이고 tail < 원소의 개수(배열 index를 벗어나지 않게 하기 위함)일 때까지 돈다.
• 현재 모든 원소의 합이 최소 합 S보다 크거나 같다면 현재 길이(tail - front + 1)와 이전에 저장해둔 길이 중 더 짧은 것을 저장해 놓고 front에 1을 더해주고, front index에 해당하는 수를 현재 원소의 합에서 빼준다.
• 현재 모든 원소의 합이 S보다 작다면 tail에 1을 더해주고, 현재 모든 원소의 합에 tail index에 해당하는 수를 더해준다.

이렇게 해서 만일 한 번이라도 모든 원소의 합이 최소 합 S보다 크거나 같다면 결과값이 갱신될 것이고, 그러지 않았다면 결과값이 갱신되지 않았을 것이다.

 

/*
* 백준 1806번 부분합
* https://www.acmicpc.net/problem/1806
* 투 포인터
*/
#include <iostream>
#include <vector>
using namespace std;

int numCnt, minSum;
vector<int> numVec;
int ans = 2000000000;

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

	cin >> numCnt >> minSum;

	int input;
	for (int i = 1; i <= numCnt; i++) {
		cin >> input;
		numVec.push_back(input);
	}

	int front = 0;
	int tail = 0;
	int curSum = numVec[0];
	while (front <= tail && tail < numCnt) {
		if (curSum >= minSum) {
			ans = min(ans, tail - front + 1);
			curSum -= numVec[front++];
		}
		else {
			tail++;
			if (tail < numCnt) {
				curSum += numVec[tail];
			}
		}
	}

	if (ans == 2000000000) {
		cout << "0";
	}
	else {
		cout << ans;
	}

	return 0;
}

위에 써둔대로 구현해주면 된다.