[백준 11053번] 파이썬 - 가장 긴 증가하는 부분 수열

 

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

11053번: 가장 긴 증가하는 부분 수열

 

 

# 조건

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하라
• A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은
• 10, 20, 30, 50 이고 길이는 4이다.

 

# 접근 방법

• dp를 이용해준다.
• 현재 인덱스의 숫자를 기준으로 이전의 숫자를 모두 훑어 준다.
• 1번부터 채워가기 때문에
• 비교하는 이전 dp 테이블의 값 +1 vs 현재 dp 테이블의 값을 비교해주면 된다.
• i=4 인 경우 j = 0 ~ 3까지의 값과 비교해주면 된다.

import sys  
input = sys.stdin.readline  
  
  
N = int(input())  
arr = [*map(int, input().split())]  
  
dp = [1 for _ in range(N)]  
  
for i in range(N):  
    for j in range(i):  
        if arr[i] > arr[j]:  
            dp[i] = max(dp[i], dp[j]+1)  
  
print(max(dp))