[DP] 백준 11053번 “가장 긴 증가하는 부분 수열” Python 풀이

문제 링크

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

풀이

• 최장 증가 부분 수열이란?
  • 각 원소가 이전 원소보다 크다는 조건을 만족하는 부분 수열 중, 가장 긴 부분 수열을 의미합니다.
• 따라서, 아래 DP 테이블과 점화식을 사용해 해결할 수 있습니다.
  • dp[i] : i번째 수를 마지막 원소로 가지는 부분 수열의 최대 길이
  • 0 ~ i-1번째 원소들을 순서대로 탐색하며, [i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + 1]을 dp[i]로 기록합니다
• 세부 동작 과정은 아래 링크를 통해 이해할 수 있습니다.
  • https://wooono.tistory.com/575

코드

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split(" ")))

# dp 테이블 초기화
dp = [1] * n

for i in range(n):
    for j in range(i):
        # i번째 수보다 작은 수에 대해서
        if (arr[j] < arr[i]):
            # dp 테이블의 i번째 길이와 [dp 테이블의 j번째 길이 + 1]을 비교한 뒤, 최댓값을 dp[i]로 기록
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))