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

문제 링크

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

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

 

풀이

동적 계획법 문제 - 점화식 도출이 안되면, 메모제이션으로 구현하도록 .. 생각... 

 

1. 주어진 배열에서 인덱스 i를 한칸 씩 늘려가면서 확인

2. 내부 반복문에서 i보다 작은 인덱스들을 살펴보며 data[j] < data[i] 인 것이 있는지 확인

3. 있다면 dp[i] 업데이트

- 기본의 dp[i]값과 dp[j]에서 마지막에 i를 추가했을 때의 길이 중 더 큰 값 

n = int(input())

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

# data[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이 
# 최솟값인 1로 초기화 
dp = [1] * n

for i in range(n):
# 본인의 왼쪽 숫자들 비교 
  for j in range(i):
  # 이전의 원소가 작은지 확인하여, 작다면 dp 최댓값 구해 +1 
    if data[j] < data[i]:
      dp[i] = max(dp[i],dp[j]+1)

print(max(dp))