[백준11053&파이썬] DP를 이용하여 반복문을 하나 줄일 수 있다.

# 문제

백준11053 가장 긴 증가하는 부분 수열 파이썬 풀이

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

# 코드

'''
  - 수열의 크기 N이 최대 1,000이기 때문에 O(N^2)을 이용한 완전탐색을 하더라도
    1,000,000 ( 약 백만 ) 안에 구할 수 있기 때문에 1초안에 구할 수 있을 것으로 보인다.
'''
import sys

N = int(sys.stdin.readline().strip())
arr = list(map(int,sys.stdin.readline().split()))

dp = [1] * (N+1)
for pivot in range(N) :
  for j in range(pivot) :
    if arr[j] < arr[pivot] :
      dp[pivot] = max(dp[pivot], dp[j]+1)

print(max(dp))

# 풀이

• 본래 3중 반복문으로 O(n^3)의 풀이가 되는 것을 DP를 사용하여 O(n^2)의 풀이로 풀이가 가능했다.
• pivot인 부분을 뽑고 해당 인덱스보다 왼쪽(작은)인덱스들을 하나씩 탐색한다.
• 이때 pivot의 value값과 iterating하는 j의 value값을 비교해야하는데, 증가는 부분수열을 찾아야하기 때문에 pivot값보다 작은지확인한다.
• 작다면 현재 계속해서 업데이팅되면서 유지중인 dp[pivot]값과 이터레이팅해서 찾은 값의 dp[j]+1보다 더 큰 값으로 dp[pivot]을 업데이트 하면 된다.