[백준] 좋다(1253)

 

이 문제는 투포인터 문제이다.

문제를 보면 눈치챘다시피 정렬을 하고 문제를 풀어야 한다.

이 문제에서 주의할 점은 Ai는 음수도 나올 수 있다는 점이다. 이 점을 숙지하고 문제를 풀어야 한다.

 

문제풀이방법

1. 배열을 정렬한다.

2. L와 R을 두고 양쪽에서 서서히 좁히면서 값을 찾는다.(L은 배열의 가장 앞, R은 배열의 가장 끝부분)

3. 만약 arr[L]+arr[R]의 값이 지금 찾고자 하는 값보다 크다면 R을--하고 작다면 L을++한다.(이 문제를 풀기 위해 꼭 떠올려야 함)

4. 만약 L과 R이 지금 찾고자 하는 값의 index와 같다면 L은 ++를 해주고 R은 --를 해준다.(이 과정을 한 뒤에는 L<R의 범위를 초과할 수도 있기 때문에 꼭 continue를 해줘서 다시 범위를 확인해줘야 한다.)

5. 만약 arr[L]+arr[R]의 값이 찾고자 하는 값과 같다면 count++를 해준다.

 

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

using namespace std;
vector<int> v;

int main(void)
{
	int N = 0;
	int count = 0;
	cin >> N;

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

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

	for (int i = 0; i < v.size(); i++)
	{
		int L = 0;
		int R = v.size() - 1;
		int num = v[i];
		
		while (L<R)
		{
			if (R == i)
			{
				R--;
				continue;
			}
			if (L == i)
			{
				L++;
				continue;
			}
			int sum = v[L] + v[R];
			if (sum > num)
			{
				R--;
			}
			else if (sum < num)
			{
				L++;
			}
			else
			{
				count++;
				break;
			}
		}
	}

	cout << count;

	return 0;
}

 

 

 

 

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

using namespace std;
vector<int> v;

int main(void)
{
	int N = 0;
	int count = 0;
	cin >> N;

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

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

	for (int i = 0; i < v.size(); i++)
	{
		int L = 0;
		int R = v.size() - 1;
		int num = v[i];
		
		while (L<R)
		{

			int sum = v[L] + v[R];
			if (sum > num)
			{
				R--;
			}
			else if (sum < num)
			{
				L++;
			}
			else
			{
				if (L != i && R != i)
				{
					count++;
					break;
				}
				else if(L==i)
				{
					L++;
				}
				else if(R==i)
				{
					R--;
				}
			}
		}
	}

	cout << count;

	return 0;
}