백준 1994 등차수열 (C++)

 

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

1994번: 등차수열

map을 이용한 dp문제였습니다.

처음에 키값을 pair형태로 사용하려해서 메모리초과가 계속 나 애를 많이 먹었습니다. 앞으로는 map에 들어가는 데이터가 많을때는 키값을 pair로 두기보다 배열형태로 pair 값 하나를 대체하는게 낫다는걸 깨달았습니다.  수열과 똑같은 크기의 배열을 만들고 각 index마다 공차를 키값으로 바텀업 dp를 하면 됩니다.

#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
map<int,int> m[2003];
int main(){
    fast_io();
    int N;
    cin>>N;
    vector<int> vec(N,0LL);
    for(auto &i : vec) {
        cin>>i;
    }
    sort(vec.begin(),vec.end());
    int ans=1;
    for(int x=0;x<N;x++){
        for(int y=x+1;y<N;y++){
            int d=vec[y]-vec[x];
            if(m[x].find(d)!=m[x].end()){
                m[y][d]=m[x][d]+1;
            }
            else m[y][d]=2;
            ans=max(ans,m[y][d]);
        }
    }
    cout<<ans;
}