[백준 파이썬] # 11053 가장 긴 증가하는 부분 수열 (복습 필요)

Siver II

# 11053 가장 긴 증가하는 부분 수열

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

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

 

풀이

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(dp[j]+1, dp[i])  # 이해되지 않는 부분..

print(max(dp))

# 연습 예제
# A = [2,11,4,55,7,9,13,3] → 5
# A = [6,2,5,1,7,4,8,3] → 4
# A = [1,2,8,2,4,8] → 4

 

후기

• LIS (Longest Increasing Subsequence)에 대한 이해가 필요하다. DP 알고리즘을 통해 이번 문제를 풀 수 있다.
    cf. 이분 탐색을 이용해서도 풀 수 있다고 한다.
  
  
• 사실 꽤 오랫동안 문제풀이에 시간을 쏟았는데 해답을 봐도 100% 이해되지 않는다.
  간단하게 풀이과정을 적어보고 넘기자.
  다시 공부해서 풀이과정에 확신이 있을 때 정리해서 올려보도록 하겠다.
  
  
• LIS를 손으로 풀어가는 과정은 자세하게 설명된 영상이 있으니 참고해 볼 것
  https://youtu.be/CE2b_-XfVDk