백준 11053 풀이 (가장 긴 증가하는 부분 수열, LIS)

요것은 머랄까 LIS인데, 나도 처음 들어봤다. 애당초 알고리즘 수업도 들어본 기억이 없기 때문에 무엇을 듣던지 생소하다. 그래서 맘편히 구글링을 해보았다.

LIS는 최장 증가 수열을 의미한다. Longest increasing Subsequence 라고 하는데

A = {10, 20, 10, 30, 20, 50} 가 존재하면 10, 20, 30, 50 이 가장 긴 수열로 존재한다. 그래서 이렇게 긴 수열이 무엇인지 찾아내는 알고리즘이다.

dp로 푸는 방법과 다른 방법도 존재한다고 하는데 나는 다이나믹 프로그래밍인 DP를 연습하고 있기 때문에 DP로 풀어보았다.

 

10, 20, 10, 30, 20, 50 이 존재한다면 각 항목별로 dp를 저장해서 누적시키는 느낌으로 풀어야 한다고 생각했다.

number	10	20	10	30	20	50
dp[i]	dp[0] = 1	dp[1] = 2	dp[2] = 1	dp[3] = 3	dp[4] = 2	dp[5] = 4

그래프를 쓰면 위와 같다. 따라서 i 인덱스에 해당되는 숫자까지 비교할때 몇번째인지 dp에 저장하면 된다.

이때 number끼리 비교하여 i에 해당되는 값이 큰경우 dp를 새롭게 갱신시킨다. 단, 갱신 시킬때 기존에 dp[i]가 가진 값보다 크거나 같다고 판단될때 dp를 갱신시킨다.

 

코드로 나타내면 아래와 같다.

n = int(input())
nl = list(map(int, input().split()))

dp = [0 for i in range(n)]
for end in range(0,len(nl)):
    if dp[end] == 0 :
        dp[end] +=1
    for i in range(0,end):
        if nl[i] < nl[end]:
            if dp[i] + 1 > dp[end]:
                dp[end] = dp[i] + 1
print(max(dp))