https://www.acmicpc.net/problem/14003

풀이:

가장 긴 증가하는 부분 수열을 구하는 문제이다.

수열의 0 ~ N 번째 까지 숫자들 중 가장 길게 증가하는 부분 수열을 만들면 된다.

배열을 하나 만든 후 수열의 숫자를 배열에 하나 씩 넣는다.

넣을 때에는 규칙이 있는데, 현재 숫자가 배열의 맨 오른쪽의 숫자보다 크다면, 가장 오른쪽에 추가해 주고, 만약 배열의 숫자 중 현재 숫자가 더 작은 숫자가 있다면, 현재 숫자로 교채해 준다.

이렇게 된다면, 배열은 자동적으로 정렬되게 되고, 최종적으로 만들어진 배열의 크기가 가장 긴 증가하는 부분 수열의 길이가 된다. (단, 이 때 배열의 원소들이 가장 긴 증가하는 부분수열이 아닐 수도 있으니 주의하자.)

가장 긴 증가하는 부분수열을 출력하기 위해서는 또 한가지 작업이 필요하다.

현재 숫자를 몇 번째 위치로 넣었는지를 확인하는 배열이 추가적으로 필요하다. 그렇게 추가적인 배열을 만들었다면, 그 배열을 거꾸로 확인하며, 가장 긴 증가하는 부분 수열을 구할 수 있다.

예제에 있는 숫자로 확인해보자.

먼저 현재 값이 10 일 때, 배열에 [10], [0] 이 들어간다.

20 일 때, [10, 20], [0, 1]

10 일 때, [10, 20], [0, 1, 0]

30 일 때, [10, 20, 30], [0, 1, 0, 2]

20 일 때, [10, 20, 30], [0, 1, 0, 2, 1]

50 일 때, [10, 20, 30, 50], [0, 1, 0, 2, 1, 3]

첫 번째 배열의 크기인 4가 가장 긴 증가하는 부분수열의 길이가 된다.

두 번째 배열을 뒤에서 부터 확인한다면, 각각 3, 2, 1, 0 의 순서로 가지고 있는 5번째(50), 3번째(30), 1번째(20), 0번째(10) 위치에 값이 가장 긴 증가하는 부분수열의 값이 된다.

예제에서는 우연히 첫번째 배열의 원소들이 가장 긴 증가하는 부분수열과 일치하지만 이런거에 속지말자.

코드:

사용언어 : python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import bisect
n=int(input())
a=list(map(int,input().split()))
c,d,e=[],[],[]
for i in a:
    s=bisect.bisect_left(c,i)
    if len(c)!=s: c[s]=i
    else: c.append(i)
    d.append(s+1)
s=len(c)
print(s)
for i in range(len(d)-1,-1,-1):
    if d[i]==s:e.append(a[i]);s-=1
print(' '.join(map(str,e[::-1])))