[백준 1940] 주몽

문제 출처: https://www.acmicpc.net/problem/1940

시간제한이 2초인데 입력으로 들어오는 N이 15000까지라서 

O(N^2)으로 풀게된다면 시간초과가 뜰 수 도있습니다..

처음엔 고유값정렬 후 처음부터 하나씩  더해가며 M이될때 카운트했는데(버블정렬 처럼)

시간복잡도가 O(N^2)이여서 92ms가 걸려서  n개의 자료를 O(NlogN)으로 이분탐색을 응용하여 다시 풀어보았습니다.

결국 제가 제출한 코드의 시간복잡도는 퀵소트O(NlogN) +이분탐색O(NlogN)으로 

O(NlogN)이라고 유추할 수 있습니다.

어떤 방식으로 푸느냐에 따라 시간차이가 상당함을 알 수 있습니다.

알고리즘은 주석으로 대체하겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;
int arr[15001];
int res = 0;

int main()
{
	int n, m;
	cin >> n >> m;
	cin.tie(0);
	cin.sync_with_stdio(false);

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	//계산의 순서를 작은값부터 탐색하기위해 정렬시킴
	sort(arr, arr + n);

	//이분탐색 응용
	int start = 0, end = n - 1;
	while (start < end)
	{
		//start+end가 m이면
		//다음 탐색할 값은 start++,end--번쨰다.
		if (arr[start] + arr[end] == m)
		{
			start++, end--;
			res++;
		}
		//start+end<m이면 작은값+큰값<M이므로 작은값++;
		else if (arr[start] + arr[end] < m)
			start++;
		//start+end>m이면 작은값+큰값>M이므로 큰값--;
		else if (arr[start] + arr[end] > m)
			end--;
	}
	cout << res;

}