[소프티어/Softeer] 징검다리 c++

징검다리 문제 링크 

 

리뷰 

최장증가수열 코드를 떠올려서 풀었다. 

최장증가수열 풀이법은 이 포스팅에 그림이 잘 그려져 있다.

 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int n, num;
vector<int> v;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  cin >> num;
  v.push_back(num);

  for(int i = 1; i < n; i++){
    cin >> num;

    for(int j = v.size()-1; j >= 0; j--){
      if(v[j] < num){
        if(j == v.size()-1) v.push_back(num); // 가장 크니까 push 
        else v[j+1] = num; // 값 교체 
        break;
      }
      if(j == 0) v[0] = num;
    }
  }
  cout << v.size();
  return 0;
}

 

 

제출 기록