문제 설명
두 개의 전봇대가 존재한다.
그 사이를 여러개의 전깃줄로 연결해 놓았다.
연결된 전깃줄이 서로 교차하지 않도록 하기위해서 몇 개의 전깃줄을 제거하려고한다.
이에 남아있는 모든 전깃줄이 교차하지 않기위해 제거해야하는 전깃줄의 최소 개수를 구해야 한다.
문제 해결 (Pseudo code 작성)
|
1
2
3
4
5
6
7
8
9
10
|
Input num_of_wire
Input connected_wires : [connected_A_pole, connectec_B_pole]
Sort connected_wires by connected_A_pole
Set connected_B_poles to sorted_connected_wires[connected_B_pole]
Set max_remaining_wire to LIS(connected_B_poles)
Set min_removing_wire to (num_of_wire - max_remaining_wire)
Print min_removing_wire
|
cs |
- Pseudo code 설명
1. 전깃줄의 갯수를 입력받는다.
2. 연결된 전깃줄들[A 전봇대, B 전봇대]을 입력받는다.
4. 연결된 전깃줄들을 A 전봇대에 연결된 기준으로 오름차순 정렬한다.
6. A 전봇대를 기준으로 정렬된 전깃줄들의 B 전봇대를 새로운 list에 저장한다.
7. B 전봇대 list의 LIS(최장 증가 부분 수열, Longest Increasing Subsequence)를 구해 최대로 유지할 수 있는 전깃줄의 갯수를 구한다.
8. 전깃줄의 최대 갯수에서 최대로 유지되는 전깃줄의 갯수를 빼서 최소로 제거해야 하는 전깃줄을 구한다.
10. 최소 제거 전깃줄을 출력한다.
시간복잡도
4. 정렬 O(nlogn)
7. LIS O(nlogn)
O(nlogn) + O(nlogn) 이므로,
최종 시간복잡도는 O(nlogn)이다.
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net