블로그 이사 중입니다 >> gumgood.github.io

2568 전깃줄 - 2 본문

Problem Solving/문제 풀이

2568 전깃줄 - 2

gumgood 2017. 5. 27. 00:13

C++11


LIS + 역추적

n이 최대 100000이기 때문에 lower_bound로 LIS를 O(nlogn)만에 구한다.

LIS문제로 바꿔주기 위해 입출력할 때 코드가 길어졌다.


A와 B사이 위치가 주어지는데 이를 A기준으로 정렬하면 B의 LIS를 구하는 문제가 된다.

여기서 다시 LIS에 속하지 않는 선을 골라 출력해야하기 때문에 코드가 더럽(?)다.

'Problem Solving > 문제 풀이' 카테고리의 다른 글

2628 종이자르기  (0) 2017.05.30
7570 줄 세우기  (0) 2017.05.27
4198 열차정렬  (0) 2017.05.27
2568 전깃줄 - 2  (0) 2017.05.27
1365 꼬인 전깃줄  (0) 2017.05.27
12837 가계부 (Hard)  (0) 2017.05.27
Tag
0 Comments
댓글쓰기 폼