[C++] 백준 1253: 좋다

문제

[C++] 백준 1253: 좋다 GOLD 4

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

 

---

 

접근 방법

이 문제는 주어진 수열에서 어떤 수가 다른 두 수의 합으로 표현될 수 있는지를 판단하는 문제이다.

 

모든 수에 대해 두 수의 합을 일일이 비교하면 시간 초과가 발생할 수 있으므로,

수열을 정렬한 뒤 투 포인터(Two Pointer) 기법을 사용한다.

 

각 원소 vect[i]를 목표 값으로 두고, 양쪽 끝에서 시작하는 두 포인터를 이동시키며
vect[start] + vect[end]가 목표 값과 같은지 확인한다.

 

구현 시 주의할 점

투 포인터를 사용하려면 반드시 수열을 정렬해야 한다.

 

두 수의 합을 구할 때 현재 찾고 있는 수(vect[i])가 덧셈에 포함되면 안 되므로, start == i 또는 end == i인 경우에는 해당 포인터를 이동시켜 제외해야 한다.

 

---

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	cin >> n;

	vector<int> vect(n, 0);
	for (int i = 0; i < n; i++)
		cin >> vect[i];

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

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int start = 0, end = n - 1;

		while (start < end)
		{
			int sum = vect[start] + vect[end];

			if (sum < vect[i])
				start++;
			else if (sum > vect[i])
				end--;
			else
			{
				if (start != i && end != i)  // 현재 찾는 수는 덧셈에 포함하지 않음
				{
					cnt++;
					break;
				}
				else if (start == i)
					start++;
				else if (end == i)
					end--;
			}
		}
	}
	cout << cnt;

	return 0;
}