[백준] 1994번 등차수열

[적용한 알고리즘]

DP

 

[아이디어]

요즘은 dp를 재귀로 풀려고 노력 중이다. 

재귀에 약했는데 익숙해져보니 재귀가 더 직관적인 거 같기도 하다. 

 

초반에 등차수열을 이루는 숫자들을 알아서 배열시키면 되므로,

배열을 우선 정렬시키는 것이 자연스러운 생각이다.

 

go(i, j) : a[j] - a[i] 를 공차로 가지는 수열의 최대 길이로 하자.

a[j] - a[i] = d 라고하면, 

a[k] = a[j] + d 를 만족시키는 k 가 존재한다면,

cache[i][j] = cache[j][k] + 1 이다. 

 

근데 문제는 k 를 찾는 방법이다. 

1. 그냥 전수조사 : (i, j) 쌍을 모조리 다 검색하는데 시간 복잡도 N^2, 전수조사에 N 이므로 시간 복잡도는 N^3 이라 TLE 난다.

2. 데이터를 정렬시켜 놨으므로, 어디있는 지 찾을 수 있는 아주 좋은 lower_bound 함수를 이용하자.

이분 탐색에 걸리는 시간 복잡도가 log N 이므로, 전체 시간 복잡도는 O(N^2logN) 으로 십가능이다.

 

그리고, 예외적으로 공차가 0인 것들은 처리가 안되므로,

미리 처리해준다. (이거 때문에 오지게 틀렸다.)

 

[교훈]

쉽지 않다. dp는

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 2001;
int N;
int cache[MAX][MAX];
vector<int> num;

int go(int i, int j){
    if (i > j) return 0;
    else if (i == j) return 1;

    int &ret = cache[i][j];
    if (ret != -1) return ret;
    ret = 2;

    int d = num[j] - num[i];
    int nxt = num[j] + d;

    int idx = lower_bound(num.begin(), num.end(), nxt) - num.begin();

    if (num[idx] == nxt) return ret = go(j, idx) + 1;
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(cache, -1, sizeof(cache));

    cin >> N;
    for (int i = 0; i < N; i++){
        int x;
        cin >> x;
        num.push_back(x);
    }
    sort(num.begin(), num.end());

    int ans = 1;
    int cnt = 1;
    for (int i = 1; i <= N; i++){
        if (num[i] == num[i - 1]){
            ans = max(ans, ++cnt);
        }
        else cnt = 1;
    }

    num.erase(unique(num.begin(), num.end()), num.end());
    //같은 수들 지워줌
    
    int N = num.size();
    for (int i = 0; i < N - 1; i++){
        for (int j = i + 1; j < N; j++){
            ans = max(ans, go(i, j));
        }
    }

    cout << ans << endl;
    return 0;
}