Baekjoon) 11053 가장 긴 증가하는 부분 수열 - Python , DP

💭 나의 접근 방법

---

증가하는 부분 수열 : 일부 혹은 전체가 오름차순인 수열을 의미한다.
문제를 읽고 다이나믹프로그래밍으로 접근하는구나를 알게 되었고, 시각화하여 점화식을 찾으려고 하였다.
list[i-1] < list[i] 를 판단하여 dp[i] = dp[i-1] +1 로 생각하였다.

다만 바로 뒤 인수만 판단하는 것은 전체 인수에서 오름차순을 찾을 수 없는 방법이었다.

따라서 이중 반복분을 이용해서 앞에있는 인수를 모두 확인하는 방법으로 접근한다.

 

 

 

💡 결과

---

# 11053 가장 긴 증가하는 부분 수열 S2
import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int,input().split()))
dp = [1]* N
for i in range(1,N):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i],dp[j]+1)
print(max(dp))

 

 

💡 느낀 점

---

다이나믹 프로그래밍을 오랜만에 풀어서 개념을 확실히 잡아야 할 것 같다. 또한 이중 반복문을 하면 시간 초과가 나지 않을까? 고민했지만 다행히 수가 길지 않았다.

 

 

 

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