두 수의 합

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	39068	13899	10428	34.896%

문제

n개의 서로 다른 양의 정수 a₁, a₂, …, a_n으로 이루어진 수열이 있다.

a_i의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다.

자연수 x가 주어졌을 때, a_i + a_j = x (1 ≤ i < j ≤ n)을 만족하는

(a_i, a_j)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다.

다음 줄에는 수열에 포함되는 수가 주어진다.

셋째 줄에는 x가 주어진다.

(1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력 1

5
1 1 1 6 0
2 7 8 3 1

예제 출력 1

18

출처

Olympiad > Balkan Olympiad in Informatics > Junior Balkan Olympiad in Informatics > JBOI 2008 6번

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog
• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 정렬
• 두 포인터

---

통과된 코드

투 포인터와 재귀를 이용하여 접근

N이 1인 경우를 조심하자

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

using namespace std;

int _N, _Res = 0, _Sum;
vector<int> _NumberV;

bool Greater(int a, int b)
{
	return a > b;
}

void TwoPointer(int _S, int _E)
{
	if (_S >= _E || _E >= _N || _S >= _N)
		return;
	if (_NumberV[_S] + _NumberV[_E] >= _Sum) {
		if (_NumberV[_S] + _NumberV[_E] == _Sum)
			_Res++;
		TwoPointer(_S + 1, _E);
	}
	else TwoPointer(_S, _E - 1);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N;
	int _Temp;
	for (int i = 0; i < _N; i++) {
		cin >> _Temp;
		_NumberV.push_back(_Temp);
	}

	cin >> _Sum;
	sort(_NumberV.begin(), _NumberV.end(), Greater);
	if (_N > 1)
		TwoPointer(0, _N - 1);
	cout << _Res;
	return 0;
}

위는 백터를 이용(동적으로 생성) / 아래는 배열로 [100000]의 공간을 미리 선언