Koala - 9기/코딩테스트 준비 스터디
[BOJ/Python] 9251번 LCS
jaehhhk
2023. 1. 15. 23:00
https://www.acmicpc.net/problem/14002
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
최장 증가 부분순열 문제.
이때 최장 증가 부분순열이란
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고,
그 길이가 최대인 부분 수열
이는 동적 계획법 문제로, dp 테이블을 만들어 풀이할 수 있다.
모든 원소가 1인 DP 테이블을 만들어주고, 조건에 따라 1을 더해주며 구한다.
이때 다음 LIS는 이전 LIS 값의 +1 한 것이다.
이 문제는 실제 증가 부분 순열을 출력하는 과정에서 '다음 LIS는 이전 LIS 값의 +1 한 것이다.' 를 역이용하여 풀이 가능하다.
최대 증가 부분 순열의 길이를 std로 두고, 반복문을 돌며 이를 하나씩 빼주며 dp 테이블에서 해당하는 값의 index를 역순으로 읽어온다.
input = __import__('sys').stdin.readline
N = int(input())
li = list(map(int, input().split()))
dp = [1 for i in range(N)]
res = []
for i in range(N):
for j in range(i):
if li[i] > li[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
std = max(dp)
for i in range(N-1, -1, -1):
if dp[i] == std:
res.append(li[i])
std -= 1
for i in res[::-1]:
print(i, end = " ")