[백준/BOJ] 백준 1994번 : 등차수열
2022. 2. 1. 21:12ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/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;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 2611번 : 자동차경주 (0) | 2022.02.01 |
---|---|
[백준/BOJ] 백준 15586번 : MooTube (Gold) (0) | 2022.02.01 |
[백준/BOJ] 백준 22988번 : 재활용 캠페인 (0) | 2022.02.01 |
[백준/BOJ] 백준 23288번 : 주사위 굴리기 2 (0) | 2021.11.23 |
[백준/BOJ] 백준 20303번 : 할로윈의 양아치 (0) | 2021.11.23 |