백준 11053 가장 긴 증가하는 부분 수열 파이썬 문제풀이 (python LIS, LCS)

문제 보러가기

 

백준 가장 긴 증가하는 부분 수열 파이썬 문제풀이

 

n = int(input())
a = list(map(int,input().split()))
dp = [0] * n

dp[0] = 1
cur = a[0]
for i in range(1, n):
    if cur < a[i]:
        cur = a[i]
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]
print(dp[n-1])

단순히 더 크면 증가하는 식으로 짜면 안된다.

 

예를 들어 

10 20 10 30 20 50 30 40 50의 경우

 

10 20 10 30 20 50 30 40 50

은 길이가 4이지만,

 

10 20 10 30 20 50 30 40 50

의 길이는 5이다.

 

처음 만나는 수열이 정답이 아닐 가능성은 항상 있다. 

그럼 어떻게 해야하지?

 

조건을 추가한다.

현재 수보다 왼쪽에, 현재 숫자보가 작은 수 중 DP가 가장 큰 값에서 +1해서 DP에 넣는 방식이다.

즉 서치가 어느정도 필요할 것 같다. 

 

n = int(input())
a = list(map(int,input().split()))
dp = [1] * n

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            dp[i] = max(dp[j] + 1, dp[i])
print(max(dp))

이렇게 왼쪽의 수들을 뒤져서 더 작은 수의 dp를 가져와서 +1한 것과,

현재 자신의 dp값 중 더 큰 쪽을 넣는다. 

그러면 부분 수열대로 숫자가 증가하는 dp가 생성된다.

 

맞았다.

이 방법을 잘 기억해놓자.