이번에는 백준 2565번 전깃줄 문제를 풀어보았습니다.
처음에는 전깃줄의 교차 여부를 직접 확인해야 할 것처럼 보이지만, A 전봇대의 위치를 기준으로 전깃줄을 정렬하면 B 전봇대의 위치가 증가하는 전깃줄끼리는 서로 교차하지 않는다는 특징을 이용할 수 있습니다.
따라서 A 전봇대를 기준으로 정렬한 뒤 B 전봇대 위치에 대해 LIS를 구하고, 전체 전깃줄의 개수에서 LIS의 길이를 빼는 방식으로 해결하였습니다.
문제 설명
A와 B 두 개의 전봇대 사이에 여러 개의 전깃줄이 연결되어 있습니다.
각 전깃줄은
(A 전봇대 위치, B 전봇대 위치)형태로 주어집니다.
서로 교차하는 전깃줄이 없도록 일부 전깃줄을 제거해야 하며, 제거하는 전깃줄의 개수를 최소로 만들어야 합니다.
결국 최대한 많은 전깃줄을 남기면서 서로 교차하지 않도록 만드는 것이 핵심입니다.
풀이 아이디어
먼저 전깃줄을 A 전봇대의 위치를 기준으로 정렬합니다.
예를 들어 다음과 같이 정렬되었다고 하겠습니다.
A : 1 2 3 4 6 7 9 10
B : 8 2 9 1 4 6 7 10A의 위치는 이미 증가하는 순서입니다.
이 상태에서 서로 교차하지 않으려면 B의 위치 역시 증가해야 합니다.
예를 들어
(A1, B8)
(A2, B2)처럼 A에서는 1 < 2인데 B에서는 8 > 2가 된다면 두 전깃줄은 서로 교차합니다.
반대로
A1 < A2 < A3
B1 < B2 < B3형태라면 전깃줄은 서로 교차하지 않습니다.
따라서 A를 기준으로 정렬한 뒤 B의 값들에서 가장 긴 증가하는 부분 수열(LIS) 을 찾으면 됩니다.
LIS에 포함되는 전깃줄은 모두 남길 수 있으므로
전체 전깃줄 개수 - LIS 길이가 제거해야 하는 전깃줄의 최소 개수가 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> lis;
vector<pair<int, int>> inp_arr;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
for (int i=0; i<N; i++) {
int a,b;
cin >> a >> b;
inp_arr.push_back({a,b});
}
sort(inp_arr.begin(), inp_arr.end());
for (int i=0; i<N; i++) {
int num = inp_arr[i].second;
auto _pos = lower_bound(lis.begin(), lis.end(), num);
if (_pos == lis.end()) {
lis.push_back(num);
} else {
*_pos = num;
}
}
cout << N-lis.size();
return 0;
}풀이 흐름
-
전깃줄의 개수
N을 입력받습니다. -
각 전깃줄의 A, B 위치를
pair<int, int>형태로 저장합니다. -
전깃줄들을 정렬하여 A 전봇대의 위치가 증가하는 순서로 만듭니다.
-
정렬된 전깃줄의 B 위치만 하나씩 확인합니다.
-
lower_bound()를 이용하여 B 위치에 대한 LIS를 구합니다. -
현재 B 위치가 기존
lis의 모든 값보다 크다면 뒤에 추가합니다. -
그렇지 않다면 현재 값 이상인 첫 번째 값을 현재 값으로 교체합니다.
-
모든 전깃줄을 처리하면
lis.size()가 교차하지 않고 남길 수 있는 최대 전깃줄의 개수가 됩니다. -
전체
N개에서 해당 개수를 빼 제거해야 하는 최소 전깃줄의 개수를 출력합니다.
구현 포인트
1. 전깃줄을 pair로 저장
vector<pair<int, int>> inp_arr;하나의 전깃줄에는 A 전봇대와 B 전봇대의 위치가 함께 존재합니다.
따라서
inp_arr.push_back({a,b});형태로 하나의 pair에 두 위치를 저장합니다.
first에는 A의 위치, second에는 B의 위치가 저장됩니다.
2. A 전봇대를 기준으로 정렬
sort(inp_arr.begin(), inp_arr.end());pair를 별도의 비교 함수 없이 정렬하면 기본적으로 first를 기준으로 오름차순 정렬됩니다.
따라서 전깃줄들이 A 전봇대의 위치 순서대로 정렬됩니다.
문제에서 같은 위치에 두 개 이상의 전깃줄이 연결되지 않는다고 했으므로 A 위치가 중복되는 경우는 없습니다.
결과적으로
A1 < A2 < A3 < A4 < ...상태를 만들 수 있습니다.
3. A를 정렬하면 B만 확인해도 되는 이유
이 문제에서 가장 중요한 부분입니다.
두 전깃줄이 다음과 같다고 하겠습니다.
(A1, B1)
(A2, B2)A를 기준으로 정렬했으므로
A1 < A2입니다.
이때 B도
B1 < B2라면 두 전깃줄은 같은 방향으로 연결되므로 교차하지 않습니다.
반대로
B1 > B2라면 A에서는 첫 번째 전깃줄이 위에 있지만 B에서는 두 번째 전깃줄이 위에 위치하게 됩니다.
따라서 두 전깃줄이 중간에서 교차하게 됩니다.
즉, A를 오름차순으로 고정한 상태에서는 B도 오름차순이 되도록 전깃줄을 선택해야 합니다.
4. 결국 B에 대한 LIS 문제
A가 이미 정렬되어 있으므로 남길 전깃줄의 B 위치는 다음 조건을 만족해야 합니다.
B1 < B2 < B3 < ...따라서 정렬된 전깃줄의 second 값들에서 가장 긴 증가하는 부분 수열을 구하면 됩니다.
int num = inp_arr[i].second;현재 전깃줄의 B 위치만 꺼낸 뒤 기존 LIS 문제와 동일하게 처리합니다.
5. lower_bound를 이용한 LIS
auto _pos = lower_bound(lis.begin(), lis.end(), num);lower_bound()는 lis에서 현재 num 이상인 첫 번째 값의 위치를 반환합니다.
현재 B 위치가 lis의 모든 값보다 크다면
if (_pos == lis.end()) {
lis.push_back(num);
}뒤에 추가하여 LIS의 길이를 증가시킵니다.
반대로 현재 값 이상인 값이 존재한다면
else {
*_pos = num;
}해당 값을 현재 값으로 교체합니다.
6. 값을 교체하는 이유
예를 들어 현재 lis가
2 6 10이고 새로운 B 위치로 7이 들어왔다고 하겠습니다.
lower_bound()는 10의 위치를 반환하므로
2 6 7로 변경됩니다.
LIS의 길이는 여전히 3이지만 마지막 값이 10에서 7로 작아졌습니다.
이렇게 마지막 값을 작게 유지하면 이후 8, 9와 같은 값이 들어왔을 때 증가 부분 수열을 더 쉽게 확장할 수 있습니다.
7. lis 자체가 실제 남길 전깃줄은 아님
vector<int> lis;여기서 lis 배열은 실제로 남길 B 위치들을 그대로 저장하는 배열이라고 볼 수는 없습니다.
lower_bound()를 이용하면서 기존 값이 계속 교체되기 때문입니다.
lis는 각 길이의 증가 부분 수열을 만들 수 있는 가장 작은 마지막 값을 관리하기 위한 배열입니다.
하지만 최종적으로
lis.size()는 LIS의 정확한 길이가 됩니다.
이 문제에서는 어떤 전깃줄을 제거했는지 출력할 필요가 없고 제거해야 하는 개수만 출력하면 되므로 LIS의 실제 원소를 복원할 필요가 없습니다.
8. LIS의 길이가 남길 수 있는 최대 전깃줄 수인 이유
A 전봇대의 위치는 이미 증가하도록 정렬되어 있습니다.
여기에서 B 위치까지 증가하도록 전깃줄을 선택하면 선택된 모든 전깃줄은 서로 교차하지 않습니다.
따라서 B 위치의 LIS는
서로 교차하지 않으면서 남길 수 있는 최대 전깃줄의 개수가 됩니다.
예를 들어 전체 전깃줄이 8개이고 B의 LIS 길이가 5라면 최대 5개의 전깃줄을 남길 수 있습니다.
그러면 나머지 3개를 제거하면 됩니다.
9. 제거해야 하는 최소 개수 계산
cout << N-lis.size();전체 전깃줄의 개수는 N입니다.
이 중 교차하지 않으면서 최대한 남길 수 있는 전깃줄의 개수가 lis.size()이므로 제거해야 하는 최소 개수는
N - LIS의 길이가 됩니다.
최대한 많은 전깃줄을 남기는 것과 최소한의 전깃줄을 제거하는 것은 같은 의미입니다.
10. 전체 로직 정리
이 문제는 전깃줄 문제를 LIS 문제로 변환하는 것이 핵심입니다.
전깃줄 (A, B) 입력
↓
A 위치를 기준으로 정렬
↓
B 위치만 확인
↓
B가 증가하는 전깃줄들은 서로 교차하지 않음
↓
B 위치의 LIS 길이 계산
↓
LIS 길이 = 남길 수 있는 최대 전깃줄 수
↓
N - LIS 길이 = 제거할 최소 전깃줄 수즉, 전깃줄의 교차 여부를 하나씩 직접 검사하는 것이 아니라 한쪽 전봇대를 정렬함으로써 반대쪽 전봇대의 LIS 문제로 바꾸는 것이 핵심입니다.
시간복잡도
먼저 N개의 전깃줄을 정렬하는 데
O(N log N)이 필요합니다.
이후 각 전깃줄의 B 위치에 대해 lower_bound()를 수행합니다.
lower_bound() 한 번의 시간복잡도는 O(log N)이고 이를 N번 수행하므로
O(N log N)입니다.
따라서 전체 시간복잡도는
O(N log N)입니다.
inp_arr와 lis에 최대 N개의 값을 저장하므로 공간복잡도는
O(N)입니다.
