BOJ 11053 가장 긴 증가하는 부분 수열

boj 11053 가장 긴 증가하는 부분 수열

D[i]가 어떻게 작동해야 문제에서 원하는 답을 잘 찾아낼 수 있을까를 생각해봤다.

위 그림과 같이 작동해야하는데, 그래서 D[i]를 i번째 원소를 마지막으로 하는 가장 긴 부분 수열의 길이라고 정의하였다. a[i]는 수열을 담는 배열이다. D[i]는 길이이기에 1씩 점점 증가하는 방식으로 식을 정의해줘야하는데, 언제 1씩 증가시켜야하는지 조건을 정해주는 것이 이 문제의 핵심이다. 먼저 코드를 보고 코드에 대해 설명해보겠다.

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

int n;
int mx;
int a[1005];
int D[1005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        D[i] = 1;

        for (int j = 1; j < i; j++)
        {
            if (a[j] < a[i] && D[j] >= D[i])
                D[i] = D[j] + 1;
        }
    }

    for (int i = 1; i <= n; i++)
        mx = max(mx, D[i]);

    cout << mx;
}

D[i]는 i번째 원소를 포함하는 가장 긴 부분 수열의 길이이므로 D[i]의 초기 값은 전부 1로 지정해준다. 앞서 말한 D[i]가 1씩 커질 수 있는 조건에 대해 설명해보자면,

• a[i] > a[j] (단, i > j)
  : 점점 증가하는 수열이기에 위 조건을 만족해야한다.
• D[j] >= D[i]
  : 이 조건을 만족하지 않으면, 어떻게 되는지 한 번 살펴보자.
  

  

  
  i가 4이고 j가 2인 경우를 지나 위 테이블과 같은 상황이 만들어졌다. D[i] >= D[i]라는 조건이 없다면, j가 3인 경우를 지날 때 아래와 같은 상황이 발생할 것이다.
  

  

  
  그렇기에 위 두 조건을 동시에 만족하는 경우에만 D[i] = D[j] + 1 을 실행한다.