[백준/python] 14002번: 가장 긴 증가하는 부분 수열 4

문제

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

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

---

문제 요약

수열이 주어졌을 때 가장 긴 증가하는 부분 수열과 그 수열의 길이를 출력한다.

---

코드

import sys
input = __import__('sys').stdin.readline

N = int(input())
# 입력 받을 수열의 길이
arr = list(map(int, input().rstrip().split()))
# 입력 받을 수열

# dp, dp_arr는 메모이제이션 테이블
dp = [1] * N
# dp[i]는 arr[i]까지 수열에서 증가하는 수열을 만들었을 때 가장 긴 수열의 길이 (초기값 1)
dp_arr = [[] for i in range(N)]
# dp_arr[i]는 arr[i]까지 수열에서 증가하는 수열을 만들었을 때 가장 긴 수열

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
        # 이전 인덱스(j) 중 현재 인덱스(i)보다 작은 arr값이 있다면,
            if dp[i] < dp[j] + 1:
            # dp[i]은 여러번 갱신될 수 있으므로 현 dp[i]와 비교해서 큰 값으로 갱신
            # 기존 dp[i]보다 발견한 dp[j]에 1을 더한 값이 더 크다면,
            # 1을 더한 이유는 dp_arr[j]에 arr[i]를 붙이기 때문
                dp[i] = dp[j] + 1
                # 더 긴 수열의 길이로 업데이트
                dp_arr[i] = dp_arr[j].copy()
                # dp_arr[i]를 더 긴 수열 dp_arr[j]의 복사본으로 업데이트 (복사본이 아니라면 얕은 복사가 된다.)
    dp_arr[i].append(arr[i])
    # 가장 긴 수열인 dp_arr[j]값으로 업데이트가 되었다면, 거기에 arr[i]값을 붙여서 업데이트
                

print(max(dp))
#print(*dp)
#print(*dp_arr)

for List in dp_arr:
    if len(List) == max(dp):
        print(*List)
        break

---

코드 설명

1. 메모이제이션 테이블 dp, dp_arr을 설정한다.

 

1 - 1. dp[i]는 arr[i]까지의 수열에서 증가하는 수열을 만들었을 때 가장 긴 수열의 길이를 저장한다. (초기값 1)

+ 초기 값이 1인 이유: 이전까지 수열에서 증가하는 수열이 자기 자신 혼자 일 경우

 

1 - 2. dp_arr[i]는 arr[i]까지 수열에서 증가하는 수열을 만들었을 때 가장 긴 수열을 저장한다.

 

2. 2중 반복문을 이용하여 인덱스 i이하 arr[j]값 중 arr[i] 값 보다 작은 값을 찾는다.

 

2 - 1. 찾은 인덱스 j의 dp[j]값과 현재 검사하고 있는 인덱스 i의 dp[i]값을 비교하여 큰 값으로 업데이트한다.

 

2 - 2. dp_arr[i] 값 역시 더 긴 수열 dp_arr[j]값으로 업데이트 한다.

 

2 - 3. 인덱스 i의 검사가 끝나서 가장 긴 수열인 dp_arr[j]값으로 업데이트가 되었다면, 거기에 arr[i]값을 붙인다.

 

3. dp 중 가장 큰 값과 dp_arr 중 가장 긴 수열을 출력한다.