[BOJ] 11053. 가장 긴 증가하는 부분 수열(DP, LIS)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

LIS의 자세한 설명은 이 문제를 참고해보자.

DP{N}은 N까지 수열에서

가장 긴 증가하는 부분 수열의 길이를 저장한다.

#. Code

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

#include <cstdio> #include <algorithm> using namespace std;   int A[1001], DP[1001];   int main(void) {     int n, i, j;     // freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++)          scanf("%d", &A[i]);          DP[1] = 1;     for (i = 2; i <= n; i++) {         int tmp = DP[i];           for (j = i-1; j >= 1; j--) {             if (A[i] > A[j])                 tmp = max(tmp, DP[j]);         }           DP[i] = tmp + 1;     }       printf("%d\n", *max_element(DP, DP+(n+1)));          return 0; } Colored by Color Scripter

cs

#. Other Code

#include <cstdio>
#include <algorithm>
using namespace std;
 
int A[1001], DP[1001];
 
int main(void)
{
    int n, i, j, res = 1;
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        int tmp = 0;
 
        for (j = 1; j < i; j++)
            if (A[i] > A[j] && DP[j] > tmp) 
                tmp = DP[j];
 
        DP[i] = tmp + 1;
        if (DP[i] > res)
            res = DP[i];
    }
 
    printf("%d\n", res);
    return 0;
}

line 13) 입력과 동시에 처리해주어서 더 효율적인 코드같다.

line 14) tmp 변수는 i-1까지 가장 긴 증가하는 부분 수열의 길이를 저장한다.

line 17) A[i]보다 작은 정수이면서, 지금까지 확인한 수열의 길이보다 더 길다면 tmp 변수에 그 길이를 저장

line 20) 앞서 구한 i-1까지의 가장 긴 증가하는 부분 수열의 길이(tmp)에 자기 자신의 개수를 더한(+1) 값을 DP[i]에 저장

line 21) 가장 긴 증가하는 부분 수열의 길이를 저장