Hanbit the Developer
[Python] 백준 2568번: 전깃줄 - 2 본문
https://www.acmicpc.net/problem/2568
2568번: 전깃줄 - 2
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결
www.acmicpc.net
먼저, 예시 입력 1의 전깃줄을 정렬하면 다음과 같다.
1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10
여기서 전깃줄이 안 꼬인다는 것은, 계속해서 값이 커져야만 한다. 즉, 가장 긴 증가하는 부분 수열을 구한다.
O(NlogN)으로 가장 긴 증가하는 부분 수열을 구하는 것은 아래 링크에 설명되어있다.
https://rccode.tistory.com/entry/14003
[Python] 백준 14003번: 가장 긴 증가하는 부분 수열 5
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,00..
rccode.tistory.com
아무튼, 이러한 생각을 하게 되어 LIS를 쓰기만 하면 이 문제는 맞게 된다. 단, 우리가 구한 LIS는 꼬이지 않는 전깃줄에 대한 것이므로, 출력할 때 이것의 차집합을 해주면 된다.
'Algorithm > 백준' 카테고리의 다른 글
| [Python] 백준 3356번: 라디오 전송 (0) | 2021.08.27 |
|---|---|
| [Python] 백준 2533번: 사회망 서비스(SNS) (0) | 2021.08.26 |
| [Python] 백준 2056번: 작업 (0) | 2021.08.25 |
| [Python] 백준 1915번: 가장 큰 정사각형 (0) | 2021.08.24 |
| [Python] 백준 14722번: 우유 도시 (0) | 2021.08.23 |
'Algorithm/백준' Related Articles
more
