[백준/BOJ] 백준 1994번 : 등차수열

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

1994번: 등차수열

중복되는 수의 개수를 세어서 등차가 0일 때 등차수열의 길이를 구하고, 중복되지 않게 수를 저장한 뒤 index1번째 숫자와 index2번째 숫자로 시작하는 등차수열의 길이를 다이나믹 프로그래밍을 이용해 문제를 해결했다. index1번째 숫자와 index2번째 숫자 뒤에 나오는 숫자를 찾을 때는 이분 탐색을 이용하여 문제를 해결했다.

 

코드

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

int n;
map<long long, int> check;
vector<long long> inputs;
int result = 0;
vector<vector<int>> cache(2000, vector<int>(2000, -1));

//inputs의 index1번째 숫자와 index2번째 숫자로 시작하는 등차수열의 길이를 구한다
int Solve(int index1, int index2)
{
	int& ret = cache[index1][index2];

	if (ret != -1)
		return ret;

	ret = 2; //최소 수열의 길이는 index1번째 숫자와 index2번쨰 숫자 두개로 이루어진 수열

	//찾으려고 하는 숫자
	int find_number = inputs[index2] + (inputs[index2] - inputs[index1]);

	//find_number가 다음에 존재하는지 확인
	int left = index2 + 1;
	int right = inputs.size() - 1;
	int index3 = -1;
	while (left <= right)
	{
		int mid = (left + right) / 2;

		if (inputs[mid] == find_number)
		{
			index3 = mid;
			break;
		}

		else if (inputs[mid] > find_number)
			right = mid - 1;

		else
			left = mid + 1;
	}

	//find_number가 없을때
	if (index3 == -1)
		return ret;

	//find_number가 있을때
	ret = 1 + Solve(index2, index3);
	return ret;
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		long long input;
		cin >> input;

		if (check.count(input) == 0)
		{
			inputs.push_back(input);
			check.insert(make_pair(input, 1));
		}

		else
			check[input]++;
	}

	//등차가 0일때 가장 긴 등차수열을 찾는다 (가장 많이 나타난 숫자의 개수)
	for (map<long long, int>::iterator it = check.begin(); it != check.end(); it++)
	{
		result = max(result, (*it).second);
	}

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

	for (int i = 0; i < inputs.size(); i++)
	{
		for (int j = i + 1; j < inputs.size(); j++)
		{
			result = max(result, Solve(i, j));
		}
	}

	cout << result;

	return 0;
}