[C++]백준(BOJ) - 1253 좋다(투 포인터)

 

난이도 : 골IV

알고리즘 유형 : 투 포인터, 이분 탐색

풀이 방법 : 투 포인터

 

문제 링크

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

 

문제 예시

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

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

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

N(1 ≤ N ≤ 2,000), 수열 |Ai| ≤ 1,000,000,000, Ai는 정수

 

예시는 간단합니다.

다른 수 두 개의 합(a[i]+ a[j]) == 어떤 수(K) && N <= 2001

-> O(n^2)이 가능하며, O(n^2) 로 풀어야함.

 

이분 탐색을 이용해 O(n^2logn) 풀이를 떠올려서 풀었지만 예외처리할 것이 많아 틀렸습니다.

알고리즘 분류를 보고 투 포인터 O(n^2) 를 확인한 뒤 투 포인터로 간단하게 풀었습니다.

 

아래는 코드입니다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, arr[2002]; 
bool IsGood[2002];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for(int i = 0; i < n; ++i)
		cin >> arr[i];

	sort(arr, arr + n);

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

		while (i < j)
		{
			if (i == k) { ++i; continue; }
			if (j == k) { --j; continue; }

			int sum = arr[i] + arr[j];

			if (sum == arr[k])
			{
			    IsGood[k] = true;
			    break;
			}
			else if (sum < arr[k])
			    ++i;
			else
			    --j;
		}
	}

	int answer = 0;

	for(int i = 0; i < n; ++i)
	     if(IsGood[i])
	          ++answer;

	cout << answer;

	return 0;
}