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

• 알고리즘 : LIS, DP, 이분탐색, lower bound

• 풀이1

  1. 수열 리스트를 돌면서 이전 원소들을 검사
  2. 현재 원소보다 작으면서
  3. 현재 위치까지의 길이 < 이전 위치까지의 길이+1 이면
  4. 현재 위치까지의 길이 갱신
  5. 갱신할 때 이전 위치 기록
  6. 이전 위치를 추적해 경로 출력

• 풀이2

  1. 수열 리스트를 돌면서
  2. 증가 리스트에서 lower bound로 값이 들어갈 최소 위치를 찾음
  3. 값 갱신 또는 추가
  4. 위치를 기록
  5. 기록한 위치를 큰 수부터 출력

코드1

# O(N^2)

def 경로출력(현재위치):
    if 이전위치리스트[현재위치] == 현재위치:
        print(수열[현재위치], end=' ')
        return
    경로출력(이전위치리스트[현재위치])
    print(수열[현재위치], end=' ')


def 초기화():
    전체길이 = int(input(''))
    수열 = list(map(int, input('').split(' ')))
    길이리스트 = [1]*전체길이
    이전위치리스트 = [i for i in range(전체길이)]
    return 전체길이, 수열, 길이리스트, 이전위치리스트, float('-inf'), 0


전체길이, 수열, 길이리스트, 이전위치리스트, 최대길이, 최대위치 = 초기화()
for 현재위치 in range(전체길이):
    for 이전위치 in range(현재위치):

        if 수열[현재위치] > 수열[이전위치]:
            if 길이리스트[현재위치] < 길이리스트[이전위치]+1:

                길이리스트[현재위치] = 길이리스트[이전위치]+1
                이전위치리스트[현재위치] = 이전위치

    if 최대길이 < 길이리스트[현재위치]:
        최대길이 = 길이리스트[현재위치]
        최대위치 = 현재위치
        
print(최대길이)
경로출력(최대위치)

코드2

# O(NlogN)

def 최소위치찾기(시작, 끝, 현재값):
    if 시작 > 끝:
        return 시작
    중간 = (시작+끝)//2
    if 증가리스트[중간] >= 현재값:
        return 최소위치찾기(시작, 중간-1, 현재값)
    else:
        return 최소위치찾기(중간+1, 끝, 현재값)


def 초기화():
    전체길이 = int(input(''))
    수열 = list(map(int, input('').split(' ')))
    return 전체길이, 수열, [], [], []


전체길이, 수열, 증가리스트, 최소위치리스트, 경로리스트 = 초기화()
for 현재위치 in range(전체길이):
    현재값 = 수열[현재위치]
    최소위치 = 최소위치찾기(0, len(증가리스트)-1, 현재값)
    최소위치리스트.append(최소위치)
    if 최소위치 < len(증가리스트):
        증가리스트[최소위치] = 수열[현재위치]
    else:
        증가리스트.append(수열[현재위치])

현재길이 = len(증가리스트)-1
현재위치 = 전체길이-1
while 현재위치 >= 0:
    if 최소위치리스트[현재위치] == 현재길이:
        경로리스트.append(str(수열[현재위치]))
        현재길이 -= 1
    현재위치 -= 1
print(len(증가리스트))
print(' '.join(reversed(경로리스트)))