[백준] 좋다 c++

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

---

 

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

//좋다 1523
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n = 0;
	int count = 0;

	cin >> n;

	vector<int> a(n, 0);

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

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

	for (int k = 0; k < n; k++)
	{
		int i = 0;
		int j = n - 1;

		long target = a[k];

		while (i < j)
		{
			if (i != k && j != k)
			{
				long sum = a[i] + a[j];

				if (sum == target)
				{
					count++;
					break;
				}
				else if (sum < target)
				{
					i++;
				}
				else
				{
					j--;
				}
			}
			else
			{
				if (j == k)
				{
					j--;
				}
				else
				{
					i++;
				}
			}
		}
	}

	cout << count;
}

 

두 개의 포인터를 이용해 값을 비교해야 할 때는 정렬을 사용해준다. 그리고 while문을 통해 target과 맞는 수 가 있는지 반복적으로 돌아주면서 더이상 비교할 수 없을때 빠져나오게한다 while(i<j)

 

if (i != k && j != k)
{
	long sum = a[i] + a[j];

	if (sum == target)
	{
		count++;
		break;
	}
	else if (sum < target)
	{
		i++;
	}
	else
	{
		j--;
	}
}
else
{
	if (j == k)
	{
		j--;
	}
	else
	{
		i++;
	}
}

우선 i와 j가 k에 포함되어 있다면 자동으로 넘어가도록 설정을 해준다. 포함되지 않는다면 두 수를 비교해 처리를 한다.

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