[BOJ] 1253 좋다 C++

개요

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

1253번: 좋다

골드4 난이도 문제다.

풀이

투 포인터를 이용하면 간단하게 풀 수 있다.

N <= 2000 이므로 배열을 정렬 후 하나하나 투 포인터로 구해주더라도 O(2000^2)로 시간 내에 연산 가능하다.

 

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 2002;

int N;
int A[LIMIT];
int ans;

void TwoPointers()
{
	int front;
	int back;
	int sum;
	for (int i = 0; i < N; i++)
	{
		front = 0;
		back = N - 1;
		while (front < back)
		{
			if (front == i)
			{
				front++;
				continue;
			}
			else if (back == i)
			{
				back--;
				continue;
			}

			sum = A[front] + A[back];
			
			if (A[i] == sum)
			{
				ans++;
				break;
			}
			else if (A[i] > sum) front++;
			else if (A[i] < sum) back--;
		}
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> A[i];

	sort(A, A + N);

	TwoPointers();

	cout << ans;
}