[BOJ][Python][실2][11722] 가장 긴 감소하는 부분 수열

문제 링크

문제링크

첫 번째 풀이

dp[i] : arr[i]를 가장 큰 수로 가지는 가장 긴 감소하는 부분 수열의 길이

LIS는 $O(n^2)$입니다.

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
import copy

# sys.stdin = open("input.txt", "r")

n = int(input())
# R, C, K = 1, n, 1
dp = [1] * n
# dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000
arr = list(map(int, sys.stdin.readline().split()))

for i in range(n - 2, -1, -1):
    for j in range(n - 1, i, -1):
        if arr[i] > arr[j] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1

print(max(dp))

Success Notice: 수고하셨습니다.