(11053) 가장 긴 증가하는 부분 수열

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

단계별로 풀어보기

21단계(동적 계획법 1) 12번째

 

 

 

아주 유명한 최장 부분 증가 수열(LIS)를 구하는 문제이다

dp[k]를 k번째 원소를 포함하는 LIS의 최대 길이라고 하자.

v[x]<v[k]라면 dp[x]에 해당하는 부분 수열에 v[k]를 덧붙일 수 있으므로 dp[x]+1은 dp[k]의 정답 후보다.

이 계산을 1≤x≤k-1인 x에 대해 전부 시행해 가능한 모든 후보값 중 최대값을 dp[k]에 저장하면 된다.

마지막으로 dp[1]부터 dp[n]까지 탐색하여 찾은 최대값이 정답이다.

 

이 코드는 dp[k]를 찾을 때 dp[1]~dp[k-1]을 탐색해야 하므로 이중 for문 때문에 시간복잡도는 O(N^2)이다.

하지만 LIS는 O(N log N)으로 풀 수 있는 더 빠른 방법이 있다.

오히려 그 방법만 기억하다보니 이 방식이 기억이 안나서 몇 번 틀렸다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n+1), dp(n+1, 1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
      if(v[j]<v[i])  dp[i]= max(dp[i], dp[j]+1);
    }
  }
  
  cout << *max_element(dp.begin(), dp.end());
  
  return 0;
}