[알고리즘] C++ 백준 1806 부분합

백준 1806

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

1806번: 부분합

풀이 전 나의 생각

N 길이의 수열이 주어질 때 연속된 수들의 부분합이 S 이상이 되는 것 중,

가장 짧은 것의 길이를 구해내야 한다.

 

조건

- N (10 ≤ N < 100,000)

- S (0 < S ≤ 100,000,000)

- 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수

 

과정

목표 값 S는 1억 이하의 수기 때문에 데이터 타입을 int로 설정해준다.

 

수열의 각 원소값도 10000이하의 자연수기 때문에 수열을 담을 배열의 데이터 타입을 int로 설정해준다.

 

원소를 더해줄 공간의 최악의 값은 10만 * 1만 = 10억이기 때문에 누적합의 타입도 int로 설정해준다.

 

N이 10만이기 때문에 2중 for문만을 사용한다면 시간제한 0.5초를 맞추지 못할 것이다.

따라서 투 포인터를 사용하여 풀어내야 한다.

 

수열의 시작지점에 시작 포인터와 끝 포인터를 설정하고 끝 포인터가 증가하며 누적합을 구한다.이 누적합이 S보다 크다면 최소 길이의 값을 갱신해주고 아니라면 S 이상의 값을 구하기 위해끝 포인터를 증가시킨다.

 

1. 현재 누적합이 S보다 같거나 크다면 최소값을 갱신해준다.

if (sum >= S)
{
	ans = min(ans, end - start);
	sum -= arr[start++];
}

수열 (5 1 3 5 10 7)이 있고 S가 15, start = 0 이라고 가정하면

5 + 1 + 3 + 5 + 10 인 부분에서 S보다 더 큰 누적합이 구해지기 때문에

if문 조건을 만족할 것이다.

 

그러면 현재 누적합의 길이인 5가 갱신되고 end 포인터는 움직일 필요가 없기 때문에

start 포인터를 하나 증가해도 여전히 누적합이 S보다 큰지, 작은지 판단해준다.

 

2. 누적합이 S보다 작다면 끝 포인터를 증가하며 새로운 누적합을 구한다.

else sum += arr[end++];

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int arr[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N, S;
	int ans = INT_MAX;

	cin >> N >> S;

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

	int start = 0, end = 0, sum = 0;

	while (start <= end)
	{
		if (sum >= S)
		{
			ans = min(ans, end - start);
			sum -= arr[start++];
		}
		else if (end == N) break;
		else sum += arr[end++];
	}

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