[BOJ] 11055. 14002, 가장 긴 증가하는 부분 수열4 (DP 기초, LIS)

#. Problem

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

* The copyright in this matter is in BOJ

#. Solve

전형적인 DP, LIS 문제이다.

자세한 동작 설명은 문제를 참고해보자.

#. Python Code

1 2 3 4 5 6 7 8 9 10

import copy N, A = int(input()), list(map(int, input().split())) dp = copy.deepcopy(A)   for i in range(1, N):     for j in range(i):         if A[i] > A[j]:             dp[i] = max(dp[i], dp[j] + A[i])   print(max(dp)) Colored by Color Scripter

cs

line 3) 자기 자신이 가장 긴 증가 부분 수열이 될 수 있으므로 수열 A를 deepcopy

line 7) j번째 정수보다 클 때, dp[i]와 dp[j]+A[i]의 max를 dp[i]에 저장

#. Cpp Code

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

################

#. Problem

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

* The copyright in this matter is in BOJ

#. Solve

11055문제의 상위(?)버전의 문제이다.

사실 똑같은데 가장 긴 증가하는 부분 수열의 길이와

가장 긴 증가하는 부분 수열을 출력해주어야 한다..

#. Code

N, A = int(input()), list(map(int, input().split()))
DP = [1 for _ in range(N)]
rev = [i for i in range(N)]
max_idx = 0
 
for i in range(N):
    for j in range(i):
        if A[i] > A[j] and DP[i] < DP[j] + 1:
            DP[i] = DP[j] + 1
            rev[i] = j
 
        if DP[max_idx] < DP[i]:
            max_idx = i
 
tmp = []
while max_idx != rev[max_idx]:
    tmp.append(A[max_idx])
    max_idx = rev[max_idx]
tmp.append(A[max_idx]), tmp.reverse()
 
print(max(DP))
for i in tmp:
    print(i, end=' ')

line 8) 증가 수열에 해당하고 부분 수열의 길이가 기존 길이보다 클 경우

line 9) DP[i]를 갱신해주고

line 10) 어떤 idx가 증가수열에 포함되었는지 저장

line 12) 최대 길이를 갖는 idx 구하기

(기존 최대 길이보다 긴 길이를 갖는 idx가 있다면 갱신)

line 16) 최대 길이를 갖는 idx가 어떤 idx를 참조했는지 확인하면서,

최대 길이 idx가 자기 자신을 참조할 때까지 반복

line 17) 참조한 정수를 tmp list에 append

line 18) 참조한 idx가 어떤 idx를 또 참조했는지 확인하기 위해 max_idx를 갱신

line 19) 처음으로 참조된 정수를 마무리로 append해주고, tmp list를 reverse (오름차순으로 출력하기 위함)