import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
A = list(map(int, input().split()))
dp = [0] * (N+1)
for i inrange(N, 0 ,-1):
count = 0for j inrange(i):
if A[i - 1] > A[j - 1]:
count += 1
dp[i] = count
print(max(dp))
실수 1 [반례가 있다.]
수열 A 가 [10, 20, 10, 30, 20, 50] 이라 하자.
그럼 50보다 작은 수는 5개 이다. dp[6] = 5개
하지만 수열 A는 정렬되어 있지 않다. 따라서 가장 긴 부분 수열이 될 수 없을 수도 있다.
설계 2
뒤에서 카운트 하니 저런 반례가 있고 딱히 더 이상 역순으로 뭔가 만들고 싶지 않다.
1이상 수열의 경우 가장 긴 증가하는 부분 수열은 항상 1이상이다.
따라서 DP테이블을 1로 초기화 해주었다.
만약 앞의 수보다 뒤의 수가 크다면 ( 10 < 20 ) 비교한 자리에서 + 1
구현한 내용을 보는 게 더 이해가 빠를 듯 하다.
구현
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
A = list(map(int, input().split()))
dp = [1] * (N+1)
for i inrange(N):
count = 0for j inrange(i):
if A[i] > A[j]:
dp[i] = max(dp[i], dp[j] + 1)
# print(dp) # [1, 2, 1, 3, 2, 4, 1]print(max(dp)) # 4
현재 O(N**2) 이다. 더 줄일 수 있는 방법을 찾아보았다.
추가로
import sys, bisect
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
A = list(map(int, input().split()))
lis = []
for num in A:
pos = bisect.bisect_left(lis, num)
if pos < len(lis):
lis[pos] = num
else:
lis.append(num)
print(len(lis))
bisect_left는 이진 탐색을 통해 리스트에서 숫자가 들어갈 위치를 빠르게 찾습니다.
LIS 알고리즘은 이진 탐색을 사용하여 O(n log n) 시간 복잡도로 해결됩니다.
if pos < len(lis):
찾은 위치 pos가 lis의 길이보다 작은지 확인합니다. 이 조건이 참이라는 것은, num이 현재 lis에서 교체될 수 있는 값이 있다는 뜻입니다.