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

1. 문제

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

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

 

 

 

2. 풀이 과정

방법 1) 자신의 앞에 있는 값들 중 자신과 작으면서 길이가 최대인 값에 1을 더한 값이 자신이 최대가 될 수 있는 값이다.

n = int(input())
arr = list(map(int, input().split()))
result = [0]*(n)
result[0] = 1

for i in range(1, n):
  max_v = 0
  #자신보다 작은 값들 중 길이가 최대인 값 고르기
  for j in range(i):
    if arr[j] < arr[i]:
      max_v = max(max_v, result[j])
  result[i] = max_v + 1

print(max(result))

 

방법 2) 들어오는 값을 결과 배열의 index로 사용한다. 결과 배열은 특정 수에서 길이가 최대가 되는 값을 저장하고 있다. 시간복잡도 측면에서 방법 1)보다 더 나은 방법이다.

n = int(input())
result = [0]*1001

for a in list(map(int, input().split())):
  result[a] = max(result[:a]) + 1 #자신보다 작은 값들 중 길이가 최대인 값 + 1

print(max(result))