• 출처 : https://www.acmicpc.net/problem/2352

• 알고리즘 : LIS, DP, 이진탐색, lower_bound

• DP만 이용한 풀이 : O(N^2), pypy3 통과

  1. 모든 수를 순회
  2. length_list에 각 인덱스를 마지막으로 하는 촤장 거리 저장
  3. 매 인덱스마다 length_list 순회

• DP+이진탐색을 이용한 풀이 : O(NlogN), python3 통과

  1. LIS 리스트 set
  2. 모든 수를 순회
  3. lower_bound를 이용해 LIS에서 현재 수 보다 같거나 큰 위치를 찾음
  4. 이미 수가 존재하면 갱신
  5. 아니면 추가

• 소감

  • LIS, lower bound, upper bound 추가 공부 필요

코드1

# 동적계획법: O(N^2)
def init():
    port_num = int(input(''))
    port_list = list(map(int, input('').split(' ')))
    return port_num, port_list


port_num, port_list = init()
length_list = [0] * port_num
for i in range(port_num):
    length_list[i] = 1
    for j in range(i):
        if port_list[j] < port_list[i]:
            length_list[i] = max(length_list[i], length_list[j]+1)
print(max(length_list))

코드2

# 동적계획법 + 이분탐색: O(NlogN)
def binary_search(start, end, key):
    if start > end:
        return start
    mid = (start+end)//2
    if key > num_list[mid]:
        return binary_search(mid+1, end, key)
    if key <= num_list[mid]:
        return binary_search(start, mid-1, key)


def init():
    port_num = int(input(''))
    port_list = list(map(int, input('').split(' ')))
    return port_num, port_list


port_num, port_list = init()
num_list = [port_list[0]]
for i in range(1, port_num):
    j = binary_search(0, len(num_list)-1, port_list[i])
    if j < len(num_list):
        num_list[j] = port_list[i]
    else:
        num_list.append(port_list[i])
print(len(num_list))