[SWEA] 9708 가장 긴 수열

문제 URL : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXDNGXlKagUDFAVX&categoryId=AXDNGXlKagUDFAVX&categoryType=CODE

SW Expert Academy

문제 접근법 :

에라토스테네스의 체를 응용하는 문제로 풀었습니다.

처음 LIS 응용문제 인줄 생각하다 도저히 접근을 못하겠어서

2차원적으로 생각 해야했었는데 그안에서도 어떻게든 시간복잡도를 줄이기위해서 생각했더니 에라토스테네스의 체 알고리즘을 응용해서 풀수 있었습니다. 중요한건 숫자가 나왔는지 확인해줘야한다는것과 나왔던 숫자안에서 최대값을 구해줘야합니다.

 

문제소스:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

//By 콩순이냉장고 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     int testcase;     cin >> testcase;     for (int test = 1; test <= testcase; test++){         int n;         cin >> n;         vector<int> v(n);         int Max = 0;         bool number[1000001] = { 0 };//나왔던 숫자인지         for (int i = 0; i < n; i++){             cin >> v[i];             Max = max(Max, v[i]);             number[v[i]] = 1;         }         sort(v.begin(), v.end());         vector<int> dp(Max + 1, 1);         int res = 1; //수열의 길이는 1이상일수밖에 없으니         for (int i = 0; i < n; i++)         {             for (int j = v[i] * 2; j <= Max; j += v[i])//에라토스테네스체를 응용             {                 if (number[v[i]])//나왔던 숫자안에서 DP계산해줘야함                     dp[j] = max(dp[v[i]] + 1, dp[j]);             }         }         for (int i = 0; i < n; i++)             res = max(dp[v[i]], res);//반드시 벡터안에 숫자들만 비교해서 결과를 내야합니다.         cout << "#" << test << " " << res << "\n";     } } Colored by Color Scripter

cs

 

모르는것 혹은 궁금한점이있으시다면 언제든 댓글을 이용해주시길 바랍니다.