백준 11053(가장 긴 증가하는 부분 수열) - python

접근

1. dp를 이용하여 dp[i]를 길이가 i일때 i번째 수로 만들 수 있는 증가하는 부분 수열의 길이로 둔다. dp[i+1]를 구하기 위해 i+1보다 더 작은 수들을 찾는다. 이 수들 중 dp의 값이 가장 큰 수를 j라고 한다면 dp[j]+1 이 dp[i+1] 이 된다.

2. 직접 가장 긴 증가하는 부분 수열을 만든다.

10 12 20 8 9 10 15 30 50 이라는 수열이 있다고 생각해보자.

arr = [0] 를 두고 arr[-1] 보다 크면 추가, 작으면 기존 수와 교체하여 구한다.

arr = [0 10 12 20] 이면 다음 수가 8이다. 이때 기존수 10과 교체한다. 이 문제는 부분 수열의 길이를 구하는 문제이기 때문에 중간에 끝나더라도  길이 자체는 그대로 출력되게 된다.

 

나의 코드(직접 세기)

import sys
input = sys.stdin.readline

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

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

print(max(dp))

 

나의코드(수열 만들기)

import sys
input = sys.stdin.readline

n = int(input())
arr=list(map(int,input().split()))
dp = [0]
for i in arr:
    if i > dp[-1]:
        dp.append(i)
    else:
        start = 0
        end = len(dp)-1
        while end-start != 1:
            mid = (start+end)//2
            if i > dp[mid]:
                start = mid
            else:
                end = mid
        dp[end] = i

print(len(dp)-1)