득이공간

[백준 C++] 1253 좋다 - 자료구조 본문

PS/알고리즘 문제풀이

[백준 C++] 1253 좋다 - 자료구조

쟁득 2024. 2. 3. 09:52
 

1253번: 좋다

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

www.acmicpc.net

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

vector<int> Sequence;

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

	int N;
	cin >> N;
	Sequence.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int Number;
		cin >> Number;
		Sequence.emplace_back(Number);
	}

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

	int Count = 0;
	for (int i = 0; i < N; ++i)
	{
		int Left = 0;
		int Right = N - 1;

		while (Left < Right)
		{
			if (Left == i)
			{
				++Left;
				continue;
			}

			if (Right == i)
			{
				--Right;
				continue;
			}

			int Sum = Sequence[Left] + Sequence[Right];

			if (Sum == Sequence[i])
			{
				++Count;
				break;
			}

			if (Sum > Sequence[i])
			{
				--Right;
			}
			else
			{
				++Left;
			}
		}
	}

	cout << Count;
}

투 포인터 문제입니다.

같은 수가 여러개 입력될 수 있다는 점과

두 포인터 이동시 구하는 수를 건너뛴다는 점을 주의해서 풀었습니다.