백준 11053 파이썬(DP)

LIS(Longest Increasing Subsequence)라는 유명한 DP 문제라고 한다.

처음봤다.

 

아이디어는 배열에 있는 숫자들을 각각 비교하면서 큰 숫자가 나올때마다 1을 더해주는 방법이다.

배열의 순서에 상관없이 증가하는 가장 긴 부분수열의 길이를 찾을 수 있다.

(배열의 최대값이 답이다)

 

# 11053번: 가장 긴 증가하는 부분 수열
# LIS(Longest Increasing Subsequence)라는 유명한 DP문제

N = int(input())

A = list(map(int,input().split()))

dp = [1] * N

for i in range(N):
    for j in range(i):
        if A[j] < A [i]:
            dp[i] = max(d[i],dp[j]+1)

print(max(dp))

참고블로그(https://source-sc.tistory.com/14)