[BOJ/C++] 1940 주몽

투 포인터를 이용하여 문제를 해결할 수 있습니다.

N이 최대 15,000이므로 $O(nlogn)$을 사용할 수 있으므로 정렬 알고리즘을 사용해도 됩니다.

1. 오름차순으로 정렬 후 시작과 끝을 투 포인터로 가르킨다.
2. 합이 M이 되는 순간 count++

// boj s4 1940
// 주몽

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M;
	vector<int> v;
	int count = 0;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	int start_idx = 0;
	int end_idx = v.size()-1;

	while (start_idx < end_idx)
	{
		if (v[start_idx] + v[end_idx] == M)
		{
			count++;
			start_idx++;
			end_idx--;
		}
		else if (v[start_idx] + v[end_idx] < M)
		{
			start_idx++;
		}
		else
		{
			end_idx--;
		}
	}
	cout << count;

	return 0;
}