백준 1940 c++ "주몽" -PlusUltraCode-

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

 

[필자 사고]

투포인터 문제이다.

 

다만 투포인터 알고리즘을 적용하기 이전에 무작위로 입력된 배열의 값들을 정렬해야 된다.

 

현재 N의 값은 15000이다. N^2알고리즘을 적용하게 되면 시간초과가 발생한다.

 

이로 인해 NlogN 알고리즘을  사용해야 된다. 현재 c++내장 정렬함수인 sort 함수를 사용하였다.

 

이제 startIdx 와 endIdx 를 사용하여 sum보다 작으면 startIdx 를 하나 증가시키고 반대의 경우는 endIdx를 감소시킨다.

 

여기서 중요한 부분은 startIdx<endIdx 인 경우만 검사해야 된다.  == 이 경우도 조사하게 되면 서로다른 두가지 조건에 위반되기 때문이다.

 

[소스코드]

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

using namespace std;

vector<int> arr;
int startIdx, endIdx;
int N, M;
int resultCount = 0;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end());
}

void GameStart() {
	startIdx = 0;
	endIdx = arr.size() - 1;

	while (startIdx < endIdx) {
		int sum = arr[startIdx] + arr[endIdx];

		if (sum == M) {
			resultCount++;
			startIdx++;
		}
		else if (sum > M) {
			endIdx--;
		}
		else {
			startIdx++;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	GameStart();
	cout << resultCount;
}