[백준/파이썬] 11053번

📍백준 11053 문제

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

코드

import sys
input = sys.stdin.readline

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

dp = [1] * n

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))

풀이

arr에서 arr[i]>arr[j]가 True 라면, dp[i] = max(dp[i],dp[j]+1) 으로 값을 바꿔준다.
arr[i] 보다 작은 위치에 있는 값들 중에 dp 테이블 값을 가장 큰 값으로 바꾸면 된다.