11053 가장 긴 증가하는 부분의 수열

https://www.acmicpc.net/problem/11053

✔ 유형 : DP(LIS)

✔ 문제 풀이: 

 

LIS(Longest Increase Sequence) 의 로직과 비슷하다.

 

DP[i] 를 i 번째 까지 가장 긴 증가하는 부분 수열의 개수라고 정의했을 때.

 

i보다 앞쪽에 있는 원소들과 비교해서 i번째의 수보다 작을 때 개수를 업데이트 한다.

 

정리하자면,

DP[i] : 현재까지 계산된 i위치에서의 LIS의 길이

DP[j] + 1 : j위치까지 LIS에 현재 원소를 추가한 길이

 

그리고 D[i] 는 위의 두 경우의 수 중 최대값으로 업데이트 해주어야한다.

 

따라서, "현재 원소를 이전 LIS 에 추가했을 때 더 긴 LIS가 되는가?"를 조건을 생각해주면 되는것이다.

 

코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

DP = [1] * N  # 모든 원소의 최소 길이는 1

for i in range(1, N):
    for j in range(i):
        if arr[i] > arr[j]:
            DP[i] = max(DP[i], DP[j] + 1)

print(max(DP))