[CLASS 4]백준 11053번 - 가장 긴 증가하는 부분 수열

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

 

DP로 구현하면 된다.

 

처음에는 이렇게 작성했었다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n = int(input())
cache = [1]*n
l = list(map(int,input().split()))
m = 1
for i in range(1,n):
    temp = []
    for k in range(i,-1,-1):
        if l[k] < l[i]:
            temp.append(cache[k])
        if temp and k == 0:
            cache[i] = max(temp) + 1
            if cache[i] > m:
                m = cache[i]

print(m)

 

이렇게 작성했고 맞았지만 속도가 좀 아쉬웠다. 그리고 방식도 최장 증가 수열을 저장하는것이 아닌, 해당 인덱스로 끝나는 최장 증가 수열의 길이를 저장한 배열이 cache배열이다.

 

그래서 다른 코드를 보고 다시 작성헀다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n = int(input())
l = list(map(int,input().split()))
cache = [l[0]]
for i in range(1,n):
    if l[i] > cache[-1]:
        cache.append(l[i])
    else:
        j = len(cache) - 1
        while j > 0 and cache[j-1] >= l[i]:
            j -= 1
        cache[j] = l[i]

print(len(cache))

 

이 방법은 cache배열을 l배열의 첫번째 값으로 초기화 한 뒤, 만약 해당 배열 마지막 값보다 큰 값이 들어오면 해당 배열의 끝에 추가하고, 아니라면 배열에서 그것보다 작은 값 바로 뒤에다가 해당 수를 삽입한다.

 

이렇게 하면 수행이 끝난 시점에 cache는 최장 증가 수열은 아닐 수 있지만, 적어도 그 길이는 최장 증가 수열의 길이임이 보장된다.