https://www.acmicpc.net/problem/2352
시간 2초, 메모리 128MB
input :
- n (1 ≤ n ≤ 40,000)
- 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트
output :
- 첫째 줄에 최대 연결 개수를 출력
조건 :
- 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다.
과거에는 도대체 어떻게 하라는 건지 몰랐다. 오늘 LIS를 공부하며 이를 통해 해결할 수 있었다.
각 포트 모두에게 연결이 되는 포트들이 있기 때문에 정렬이나 다른 것들은 필요가 없다.
4 2 6 3 1 5로 입력이 될 때
4 와 2의 경우 겹치게 되는데 이 때 더 낮은 2를 고르고
그 다음 6을 택하면 겹치지 않으니 [2, 6]
3의 경우 6과 겹치니 [2, 3]
1의 경우 다른 둘과 겹치니 무시 혹은 이분탐색 시에는 [1, 3]
그 다음 5는 추가 할 수 있으니 [1, 3, 5]를 가지고 올 수 있다.
이는 물론 꼬이는 위치지만 모든 배열에 대해서는 결국 가장 적합한 증가하는 부분 수열이다.
물론 순서를 고려 하지 않았지만 말이다.
정확하게 얻으려면 다른 인덱스가 필요하다.
암튼 이런 문제의 경우 증가하는 부분 수열이 필요하다.
import sys
from bisect import bisect_left
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
temp = [data[0]]
for i in range(1, n):
if temp[-1] < data[i]:
temp.append(data[i])
else:
idx = bisect_left(temp, data[i])
temp[idx] = data[i]
print(len(temp))
