[c++] 백준 14003 - 가장 긴 증가하는 부분 수열 5(dp)

0. [c++] 백준

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

1. 풀이

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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include<iostream> #include<vector> #include<algorithm> #include<queue>   using namespace std;   int N;   void solve() {     vector<int> A;     vector<pair<int, int> > Arr;     int temp;       cin >> temp;     A.push_back(temp);     Arr.push_back({ 0, temp });       for (int i = 1; i < N; i++) {         cin >> temp;                  if (A[A.size() - 1] < temp) {             Arr.push_back({ A.size(), temp });             A.push_back(temp);                      }         else {             for (int j = 0; j < A.size(); j++) {                 if (A[j] >= temp) {                     Arr.push_back({ j, temp });                     A[j] = temp;                     break;                 }             }         }     }       cout << A.size() << endl;       vector<int> ret;     int num = A.size() - 1;     for (int i = N - 1; i >= 0; i--) {         if (Arr[i].first == num) {             ret.push_back(Arr[i].second);             num--;         }     }     reverse(ret.begin(), ret.end());     for (int i = 0; i < ret.size(); i++) {         cout << ret[i] << " ";     }   }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> N;     solve(); } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!