[백준] 11053번 가장 긴 증가하는 부분 수열

백준_11053

유명한 dp 문제 유형 중 하나인 '가장 긴 증가하는 부분 수열(LIS)'
이번 기회에 LIS 유형을 모두 시도해볼까 한다
여러번 풀어도 풀이를 까먹으니.. 이번 기회에 제대로 이해하고 넘어가야지

그리고 마지막 print문에서 dp[n-1]를 해주면 틀린다. 예를 들어 10 20 50 10에서 답은 3이지만, 가장 마지막 자리를 print하면 1이 되기 때문이다.

n = int(input())
nums = list(map(int, input().split()))
dp = [0]*n

for i in range(n):
    for j in range(i):
        #i보다 작고 앞에 있는 숫자 중에서 가장 긴 길이 구하기
        if nums[i]>nums[j] and dp[i]<dp[j]:
            dp[i] = dp[j]
    #i 본인의 갯수 더하기
    dp[i]+=1
print(max(dp))