※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 3066번 문제인 브리징 시그널이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/3066
3066번: 브리징 시그널
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽
www.acmicpc.net
서로 교차하지 않는 최대 시그널의 개수는 LIS의 크기와 같다는 점을 관찰해내자.
즉, 이 문제는 각 테스트케이스마다 LIS의 크기를 구해서 출력하는 문제이다.
(세그먼트트리로 LIS 구하기 연습4)
아래는 제출한 소스코드이다.
728x90
'BOJ' 카테고리의 다른 글
| [BOJ 3745 // C++] 오름세 (0) | 2021.07.01 |
|---|---|
| [BOJ 1568 // C++] 새 (0) | 2021.07.01 |
| [BOJ 1264 // C++] 모음의 개수 (0) | 2021.07.01 |
| [BOJ 16769 // C++] Mixing Milk (0) | 2021.07.01 |
| [BOJ 2638 // C++] 치즈 (0) | 2021.06.30 |