295번째 문제 - 1994 등차수열

주어진 수열에서 최장 등차수열을 찾는 문제이다. 최근에 푼 문제 중에서 제법 어려운 편인것 같다.

일단 d[i][j]를 수열에서 i번째수와 j번째수로 시작하는 등차수열의 최대 길이로 잡았다.  이 발상을 하는데 혼자 고민을 한시간 넘게했다.

그 후에 동적 계획법 함수 dp 안에서 first, second로 third를 찾는데 순차 탐색을 하니 전체 시간복잡도가 O(n^3)이 되어서 시간이 모자랐다. 시간 문제를 해결 하기위해 순차 탐색 대신에 이진탐색을 수행하였는데 여기서도 예외가 발생했다. 같은 수가 여러개 있는 상황을 고려하지 못했다. third가 될 수 있는 수가 여러개가 있다면 가장 왼쪽의 수를 선택해야한다. 이는 stl::low_bound 함수로 구현했다.

d[first][second] : first번째 수와 second번째수로 시작하는 등차 수열의 최대 길이.

d[first]second] = d[second][third] + 1 (third는 이진탐색으로 찾음)

시간 복잡도 : O(n^2 log n) 

#include <iostream>

#include <vector>

#include <cstdio>

#include <algorithm>

#include <memory.h>

using namespace std;

int C,t;

vector<int> seq;

int d[2001][2001];

int dp(int first, int second)

{

int &ret = d[first][second];

if(ret != -1) return ret;

int idx = -1;

   int  third = 2*seq[second]-seq[first]

auto low = lower_bound(seq.begin()+second+1,seq.end(), third );

if(low != seq.end() && *low == third ) idx = low-seq.begin();

if(idx == -1) return ret = 2;

else return ret = 1+dp(second, idx);

}

int main()

{

scanf("%d",&C);

for(int i=0; i<C; i++)

{

scanf("%d",&t);

seq.push_back(t);

}

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

memset(d,-1,sizeof(d));

int ans = 1;

for(int i=0; i<C; i++)

{

for(int j=i+1; j<C; j++)

{

ans = max(ans,dp(i,j));

}

}

cout<<ans;

}