[백준 / BOJ] C++ 11053 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

 

문제

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

11053번: 가장 긴 증가하는 부분 수열

 

 

풀이

가장 긴 증가하는 부분 수열 LIS(Longest Increasing Subsequence)를 이용한 문제다. O(N^2)가 걸리는 dp를 사용한 풀이로 풀린다. dp는 해당 index에서 끝나는 가장 긴 증가하는 부분 수열을 의미한다. 모든 수는 길이가 1인 증가하는 부분 수열이므로 dp를 모두 1로 초기화한다. 그리고 i = 0부터 N-1까지 증가하며 차례대로 j = 0부터 i-1까지 v[j]가 v[i]보다 작은 값 중 dp[j]가 가장 큰 값 + 1을 dp[i]로 한다. 그리고 dp 배열에서 가장 큰 원소를 출력하면 된다.

v[0]은 첫 번째 원소이므로 dp[0] = 1

v[0]이 v[1]보다 작으므로 dp[1] = dp[0] + 1 = 2

v[2]보다 앞에 작은 원소가 없으므로 dp[2] = 1

v[3]보다 작은 원소들 중 dp값이 가장 큰 원소는 v[2]이므로 dp[3] = dp[2] + 1 = 3

v[4]보다 작은 원소는 v[0] 또는 v[2]이다. 모두 dp 값이 1 이므로 dp[4] = dp[0 or 2] + 1 = 2

v[5] 보다 작은 원소 중 dp[3]이 가장 크기 때문에 dp[5] = dp[3] + 1 = 4

모두 탐색을 마쳤으므로 dp 배열에서 가장 큰 원소인 4를 출력하면 답이다.

 

 

코드

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

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