[BOJ] #11053_가장 긴 증가하는 부분 수열(Python3, 파이썬)

본 게시글은 백준 저지 알고리즘 문제를 '파이썬, Python3' 언어로 풀이한 내용을 주관적으로 정리하였으며, 내용과 관련된 코드리뷰 및 피드백 환영합니다.

티어

Silver II

문제 출처

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

---

풀이

import sys 
input = sys.stdin.readline

n = int(input()) # 수열의 크기 
a = list(map(int, input().split())) # 10 20 10 30 20 50

dp = [0 for i in range(n)]
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]

    dp[i] += 1

print(max(dp))

 

첫 번째 숫자부터 검사를 하면 되는데, 자기 자신보다 작은 숫자들 중 가장 큰 길이를 구하고, 그 길이에 +1을 해주면된다.