문제 접근
유명한? DP문제다.
작은 문제로 쪼개보면 우리는 LIS[i] = A[0] … A[i] 부수열에 대해, A[i]로 끝나는 증가 부수열 중에서 가장 긴 부문자열의 길이라고 정의해보자.
정답 LIS는 A[0], A[1], …, A[n-1] 중 하나의 값으로 반드시 끝나므로 LIS 길이는 max(LIS[i])가 됨을 알 수 있다.
num[i]를 마지막에 가지는 LIS는 A[j] < A[i]인 모든 j에 대해, LIS[i] = maxj (LIS[j] + 1)의 값을 가진다.
문제 풀이
총 2개의 반복문을 사용하여 O(N^2)의 시간복잡도를 가진다.
num[i]보다 작은 num[j]를 마지막으로 가지는 부분수열들 중 최댓값에 1을 더하는 것이 이 문제 풀이의 핵심이라고 볼 수 있다.
def lis():
for i in range(1, N): # 1부터 끝까지
for j in range(i-1, -1, -1): # i번째 인덱스보다 1작은 곳부터 0까지
if num[j] < num[i]: # num[i]가 뒤에 붙으려면 당연히 그 전의 수가 더 작아야 함
dp[i] = max(dp[i], dp[j] + 1) # 마지막이 num[j]로 끝나는 가장 긴 수열 뒤에 num[i]를 붙임
return max(dp) # 가장 긴 문자열의 길이 반환제출 코드
T = int(input())
def lis():
for i in range(1, N): # 1부터 끝까지
for j in range(i-1, -1, -1): # i번째 인덱스보다 1작은 곳부터 0까지
if num[j] < num[i]: # num[i]가 뒤에 붙으려면 당연히 그 전의 수가 더 작아야 함
dp[i] = max(dp[i], dp[j] + 1) # 마지막이 num[j]로 끝나는 가장 긴 수열 뒤에 num[i]를 붙임
return max(dp) # 가장 긴 문자열의 길이 반환
for test_case in range(1, T + 1):
N = int(input())
dp = [1 for i in range(N)]
num = list(map(int, input().split()))
print(f'#{test_case} {lis()}')
