[코테]99클럽 코테 스터디 37일차 TIL 백준 11053 가장 긴 증가하는 부분수열

꽤나 유명한 DP문제이다. 사실 DP문제는 굉장히 자신이 없어서 한 5분 정도 고민하고 바로 답을 봤다.. 

dp[i]를 정의하는 것부터 꽤나 접근이 어려웠다. 

dp[i]를 i번째 원소를 가장 마지막으로 하는 증가하는 부분수열의 최대 길이라고 한다. 

그리고 모든 원소는 자기 자신을 부분수열로 가질 수 있으므로, dp 초기 테이블을 dp = [1] * N으로 잡을 수 있다. 

예제를 표로 그려보면, 다음과 같다. 

인덱스 i	A[i]	dp[i] 초기값
0	10	1
1	20	1
2	10	1
3	30	1
4	20	1
5	50	1

 

이전 dp 테이블 값 + 1 과 자기 자신의 dp 테이블 값을 비교했을 때 큰 값을 현재 자신의 dp 테이블 값으로 설정하는 점화식을 세우면 끝난다. 

i = 1, A[1] = 20

• j = 0: A[0] = 10 < A[1] → dp[1] = max(1, dp[0] + 1) = 2
• dp = [1, 2, 1, 1, 1, 1]

i = 2, A[2] = 10

• j = 0, j = 1: A[j] > A[2] → 패스
• dp = [1, 2, 1, 1, 1, 1] (변화 없음)

i = 3, A[3] = 30

• j = 0: A[0] = 10 < A[3] → dp[3] = max(1, dp[0] + 1) = 2
• j = 1: A[1] = 20 < A[3] → dp[3] = max(2, dp[1] + 1) = 3
• j = 2: A[2] = 10 < A[3] → dp[3] = max(3, dp[2] + 1) = 3
• dp = [1, 2, 1, 3, 1, 1]

i = 4, A[4] = 20

• j = 0: A[0] = 10 < A[4] → dp[4] = max(1, dp[0] + 1) = 2
• j = 1, j = 2, j = 3: A[j] > A[4] → 패스
• dp = [1, 2, 1, 3, 2, 1]

i = 5, A[5] = 50

• j = 0: A[0] = 10 < A[5] → dp[5] = max(1, dp[0] + 1) = 2
• j = 1: A[1] = 20 < A[5] → dp[5] = max(2, dp[1] + 1) = 3
• j = 3: A[3] = 30 < A[5] → dp[5] = max(3, dp[3] + 1) = 4
• dp = [1, 2, 1, 3, 2, 4]

import sys

read = sys.stdin.readline

N = int(read())

numbers = list(map(int, read().split()))

# dp[i] = i번째 원소를 마지막 원소로 하는 가장 긴 부분수열의 길이

# dp 테이블 초기화

dp = [1] * N

for i in range(1,N):

    for j in range(i):

        if numbers[j] < numbers[i]:

            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))