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

투포인터 문제입니다.

n개의 수열이 주어지고
n개의 수열중 인접한 수들을 더해서 m을 만들 수 있는
최소한의 덧셈의 횟수를 구하는 문제입니다.

1. 포인터 x를 제자리에 두고 포인터 y를 m이 될때까지 더하면서 이동합니다.
2. m이 되거나 넘었으면 count를 최소값과 비교해서 작으면 넣습니다.
3. x를 한칸씩 이동하면서 m이 되지 않을때까지 위치에 있는 배열값을 뺍니다. count도 감소.
4. m보다 낮아졌으면 다시 1~3을 반복합니다.

위와같은 방법으로 count중 가장 최소값인것을 찾을 수 있습니다.

 

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

int main(int argc, char* argv[])
{
	int n, m;
	int i, j;
	int flag = 0;
	int num = 0;
	int count = 0;
	int minNum = 987654321;
	int arr[100010];

	memset(arr, 0, sizeof(arr));

	cin >> n;
	cin >> m;

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

	for (i = 0, j = 0; i < n; ++i) {
		num += arr[i];
		++count;

		while (num >= m) {
			minNum = min(minNum, count);
			num -= arr[j];
			++j;
			--count;
			flag = 1;
		}
	}

	if (flag == 0) {
		cout << "0" << endl;
		return 0;
	}
	cout << minNum << endl;

	return 0;
}