[Baekjoon] 11053번 : 가장 긴 증가하는 부분 수열 (Python)

[Baekjoon] 11053번 : 가장 긴 증가하는 부분 수열 (Python)

 

목차

 

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

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

Python

 

방법 1 - 메모리 30864KB / 시간 152ms / 코드 길이 187B

 

1. 다음 점화식 조건을 만족하는 것을 우선 찾는다.

1) i번째 이전의 모든 숫자에 대해 증가하는 것이 분명한 것

2) 1)을 만족하는 dp의 memorization 중 가장 큰 것

 

2. 찾은 조건에서 dp의 memorization 값 + 1한 것이 i 번째의 dp memorization 값이다.

 

 

n=int(input())
l=list(map(int,input().split()))
d=[0]*n
for i in range(n):
    for j in range(i):
        if l[i] > l[j] and d[i]<d[j]:
            d[i] = d[j]
    d[i] += 1
print(max(d))

 

방법 2 - 메모리 30864KB / 시간 204ms / 코드 길이 172B

 

기본적으로 모든 초기값을 1로 준다.

i번째의 값과 0~i-1의 값들을 모두 비교하며 i 번째의 값이 클 때

i번째 dp memorization와 위에 해당하는 j 번째 dp memorization + 1 중 큰 값을 i번째 dp memorization으로 설정한다.

$$d[i] = max(d[i], d[j]+1)$$

 

큰 틀에서는 방법 1과 유사하다.

 

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