[BOJ] 가장 긴 증가하는 부분 수열

 

 

코드 

 

t = int(input())
num = list(map(int,input().split()))
dp = [1] * t

for i in range(t):
  for j in range(i):
    if num[i] > num[j]:
      dp[i] = max(dp[i],dp[j]+1) # 현재의 dp값과 이전 수의 dp값에 1을 더한 값을 비교 후 더 크면 갱신
print(max(dp))

분석 > LIS(Longest Increasing Subsequence) 알고리즘으로 원리는 간단하다. 현재의 수 (num[i]) 가 비교대상이 되는 이전의 수 (num[j]) 보다 클 때만, 비교 대상이 되는 수의 dp값에 1을 더한 값을 갱신하는 것이다. 그렇게 이전의 수들을 모두 탐색하면, 최종적으로 현재 수의 dp값은 이전 수 중에서 가장 큰 크기의 dp값에 1을 더한 값이 된다. 그렇게 해서 형성된 배열에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이가 된다. 

 

 

 

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