[백준] 1253 좋다 - C++

문제) N개의 수 중 어떤 수가 다른 두 수의 합으로 나타낼 수 있으면 좋은 수라고 한다. 좋은 수의 개수를 구하는 프로그램을 만들어보자.

    첫째 줄에 수의 개수 n, 둘째 줄에 정수 n개가 주어진다.

    시간 제한은 2초, 메모리 제한은 256MB이다.

 

투포인터 알고리즘을 사용하는 문제이다. 숫자가 정수이기 때문에 음수나 0이 들어올 수 있다는 걸 염두해두고 문제를 풀어야 한다. 그렇기 때문에 수를 구할 때 자기 자신은 제외하고 카운팅 해야 한다.

 

k는 0부터 n까지
    i가 j보다 작을 때까지
        arr[i]+arr[j]값이 arr[k]값과 같다면
            i와 j가 k가 아니라면
                카운팅 추가 후 반복문 종료
            i나 j가 k라면
                상황에 맞게 포인터를 옮긴 후 계속 수행
        합한 값이 k보다 작다면
            i값 올리기
        아니라면
            j값 내리기

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

	int n;
	cin >> n;

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

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

	int cnt = 0;

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

		while (i < j)
		{
			if (vec[i] + vec[j] == find)
			{
				if (i != k && j != k)
				{
					cnt++;
					break;
				}
				else if (i == k)
				{
					i++;
				}
				else if(j == k)
				{
					j--;
				}
			}
			else if (vec[i] + vec[j] < find)
			{
				i++;
			}
			else
			{
				j--;
			}
		}
	}

	cout << cnt << '\n';

	return 0;
}