[백준/BOJ] 백준 1253번 : 좋다

www.acmicpc.net/problem/1253

1253번: 좋다

두 수의 합이 어떤 수가 맞는지 확인하므로 수를 정렬한 뒤 right가 오른쪽 끝(n-1)에서 시작하는 투 포인터 (중간에서 만나기?)를 통해 문제를 해결했다.

 

코드

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

int n;
vector<int> a;

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		a.push_back(input);
	}

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

	int result = 0;
	for (int i = 0; i < n; i++)
	{
		int check_index = i; //확인하는 값의 index
		int left = 0;
		int right = n - 1; //right가 n-1에서 시작하는 투포인터 (중간에서 만나기?)
		int sum;

		while (1)
		{
			if (left == check_index)
				left++;
			if (right == check_index)
				right--;
			if (left >= right)
				break;

			sum = a[left] + a[right];

			if (sum == a[check_index]) //값이 같을때
			{
				result++;
				break;
			}

			else if (sum > a[check_index]) //더 클때
			{
				right--;
			}

			else if (sum < a[check_index]) //더 작을때
			{
				left++;
			}
		}
	}

	cout << result;

	return 0;
}