[백준 C++] 1253 : 좋다

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

간단하게 생각하면 모든 수를 하나씩 더해봐서 할 수 있는 간단한 문제이다.

다만, N의 최대값은 2,000인데 시간복잡도에 따라 N^2 or N^3 등등 커질수록 많은 시간이 걸릴 것이다.
그렇게 되면 시간초과에 걸리게 된다.

즉, 이 문제를 풀기 위해서는 그 이하의 시간복잡도를 가지는 알고리즘을 사용하여 문제를 풀어야 한다.

---

두 개의 합으로 나타낼 수 있는 수를 찾는 문제이므로, 투 포인터 알고리즘을 사용한다.

시작 인덱스 0과, 끝 인덱스 N - 1에서 차례차례 더해서 확인해가며 값을 찾으면 시간복잡도 O(N)으로 값을 찾을 수 있다.

그 작업을 수행하기 위해서는 정렬을 먼저 수행하여 두 수를 더해 그 값을 비교하여 합이 작으면 시작 인덱스를 키우고, 작으면 끝 인덱스를 줄여가면서 값에 근접하면 된다.

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

using namespace std;

int N;
vector<int> list;

int calculate()
{
	int answer = 0;
	int i, j;

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

		while (i < j)
		{
			if (list[i] + list[j] == list[k])
			{
				if (i != k && j != k)
				{
					answer++;

					break;
				}
				else if (i == k)
				{
					i++;
				}
				else if (j == k)
				{
					j--;
				}
			}
			else if (list[i] + list[j] < list[k])
			{
				i++;
			}
			else
			{
				j--;
			}
		}
	}

	return answer;
}

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

	cin >> N;
	int temp;

	for (int i = 0; i < N; i++) 
	{
		cin >> temp;
		list.push_back(temp);
	}

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

	cout << calculate() << endl;

	return 0;
}

간단하게 설명하자면

내장되어있는 sort를 사용해 O(NlogN)으로 정렬해준다. (sort()함수는 기본적으로 이 시간복잡도를 만족한다.)

이 후 시작인덱스 i, 끝 인덱스 j를 이용해 값에 접근해준다.

i가 j보다 클 때까지 진행하면서 합이 작으면 i를 크게, 크면 j를 작게 해준다.

값이 같을 때에는 answer을 올려주지만, 만약 그 값이 k와 같게 된다면 정답 본인을 포함하는 것이기 때문에 제외시켜주는 작업을 수행한다.