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

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15

5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

 

<코드>

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

long long sum, S;
long long prefix_sum[100001];
int Min = 100000;
int N, x;

int main()
{
	int mid, left, right;

	cin >> N >> S;

	for (int i = 1; i <= N; i++)
	{
		cin >> x;
		sum += x;
		prefix_sum[i] = sum;
	}

	for (int i = 0; i < N; i++)
	{
		left = i;
		right = N;
		while (left <= right)
		{
			mid = (left + right) / 2;

			if (prefix_sum[mid] - prefix_sum[i] < S)
				left = mid + 1;
			else
			{
				right = mid - 1;
				Min = min(Min, mid - i);
			}
		}
	}

	if (Min == 100000) cout << 0;
	else cout << Min;
}

 

풀이 방법

이중 for문으로 코드 작성 시 간단하게 구할 수 있는 문제이지만 시간초과가 발생할 가능성이 높기 때문에 이분탐색을 사용하였다. 따라서 시간복잡도는 O(NlogN)으로 풀이가 가능하다.

그리고 prefix sum의 경우 처음에 수열을 입력받을 때 기록을 해놓으면 쉽게 부분합을 구할 수 있다.

ex) prefix_sum[4] - prefix_sum[1] = 수열의 2번째 원소부터 4번째 원소까지의 부분합

 

 

 

www.acmicpc.net/problem/1806

1806번: 부분합