문제

문제 링크

해설

• 전형적인 투포인터 문제입니다.
• 수열의 길이가 최대 10만이므로 O(N²)이 소요되는 bruteforce로는 풀 수 없습니다.
• 우선, 수열을 오름차순으로 정렬합니다. (O(NlogN))
• 수열에서 더할 두 값을 left와 right이라는 포인터로 지정한 뒤
  • 더한 값이 X보다 크다면 right을 감소,
  • 더한 값이 X보다 작다면 left를 증가,
  • 더한 값이 X와 같다면 정답 경우의 수를 1개 카운팅합니다.
  • 이 과정을 right과 left가 서로 교차할 때까지 반복합니다.

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N;
	cin >> N;

	vector<int> v(N);
	for (int i = 0; i < N; ++i) cin >> v[i];
	
	int X;
	cin >> X;
	
	sort(begin(v), end(v));
	
	int ans = 0, left = 0, right = N - 1;
	while (right > left) {
		int sum = v[left] + v[right];
		if (sum > X) right--;
		else if (sum < X) left++;
		else ans++, left++, right--;
	}
}

소스코드 링크

결과