[C/C++] 백준 2003번 - 수들의 합 2

 

 

 

 

<코드>

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

int x, N, M, ans, sum;
int prefix_sum[10001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int s, e, mid;

	cin >> N >> M;

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

	for (int i = 0; i <= N; i++)
	{
		s = i;
		e = N;

		while (s <= e)
		{
			mid = (s + e) / 2;

			if (M > prefix_sum[mid] - prefix_sum[i])
			{
				s = mid + 1;
			}
			else if (M < prefix_sum[mid] - prefix_sum[i])
			{
				e = mid - 1;
			}
			else
			{
				ans++;
				break;
			}


		}
	}

	cout << ans;
}

 

풀이 방법

시간 제한이 0.5초이고 N의 값이 최대 1만이기 때문에 이분탐색을 이용하여 NlogN의 시간복잡도로 풀이하였음.

 

www.acmicpc.net/problem/2003

2003번: 수들의 합 2