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

접근

• 11503. 가장 긴 증가하는 부분 수열에서 길이 외에 수열을 추가로 출력해야하는 문제이다.

• 길이를 구하는 과정까지는 동일하지만, 이후 구해진 길이를 바탕으로 수열을 구하는 코드를 추가하는 쪽으로 접근했다.

구현 과정

※ 가장 긴 증가하는 부분 수열을 LIS라고 한다. ※ 가장 긴 증가하는 부분 수열의 길이를 max_d라고 한다.

1. max_d를 바탕으로 LIS에서 가장 마지막 수를 찾아 그 인덱스를 저장한다.
2. LIS의 나머지 수는 마지막 수보다 왼쪽에 있으므로 저장한 인덱스-1부터 거꾸로 for문을 돈다. i. 다이나믹 테이블의 값이 max_d - 1이고, 그 수가 LIS의 마지막 값보다 작다면 LIS에 추가(append)한다. ii. 다음 수를 찾아야 하므로 max_d에서 1을 뺀다.
3. for문을 모두 돌았다면 LIS가 리스트에 거꾸로 저장되어있을 것이다. 이를 거꾸로 출력하면 답이 된다.

코드

import sys
input = sys.stdin.readline

if __name__=="__main__":
    N = int(input())
    A = list(map(int,input().split()))
    d = [0 for _ in range(N)]
    idx = [A[0]]
    d[0] = 1
    # 길이 구하는 과정
    for i in range(1,N):
        for j in reversed(range(i)):
            if A[i] > A[j] and d[i] <= d[j]:
                d[i] = d[j] + 1
        if d[i] == 0:
            d[i] = 1
            
    # LIS 구하는 과정
    max_d = max(d)
    max_idx = d.index(max_d) # 1 과정, max_d가 여러개일 경우 index를 이용하면 가장 앞의 값을 찾을 수 있다.
    LIS = [A[max_idx]] # LIS에 현재 값을 추가
    for k in reversed(range(max_idx)):
        if d[k] == max_d-1 and A[k] < LIS[-1]: # 2-i 과정
            LIS.append(A[k])
            max_d -= 1 # 2-ii 과정
    print(max(d))
    print(*reversed(LIS)) # 3 과정

다른 접근법

• 길이를 구하는 과정과 수열을 구하는 과정을 별도로 하지 않고, 동시에 할 수 있다.

먼저 코드부터 보면

import sys
input = sys.stdin.readline

def get_LIS(idx):
    if idx == -1:
        return
    else:
        get_LIS(v[idx])
        print(A[idx], end=" ")

if __name__=="__main__":
    N = int(input())
    A = list(map(int,input().split()))
    d = [0 for _ in range(N)]
    v = [-1 for _ in range(N)]
    d[0] = 1
    for i in range(1,N):
        for j in reversed(range(i)):
            if A[i] > A[j] and d[i] <= d[j]:
                d[i] = d[j] + 1
                v[i] = j
        if d[i] == 0:
            d[i] = 1
    max_d = max(d)
    max_idx = d.index(max_d)
    print(max_d)
    get_LIS(max_idx)

• v 리스트는 증가수열에서 자신의 직전 수 인덱스를 저장한다.
  • 말이 어려운데, A[v[i]]가 증가 수열에서 A[i]의 이전 수에 해당한다.
• LIS에서 가장 마지막 수부터 거꾸로 LIS를 탐색하는 get_LIS라는 함수를 이용한다.

• get_LIS 함수는 위 그림과 같이 동작한다.
• return 이후에 print를 하므로 A[3]부터 재귀를 거슬러 올라가며 출력하게 된다.