개요
-
입력
첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다. -
출력
전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.
접근방식
-
최소의 전선을 잘라내려면 최대한 많이 안 꼬이고 평행해야한다.
-> 결국 전체 크기에서 제일 긴 증가하는 부분수열값을 빼면 된다. -
그냥 제일 긴 증가하는 부분수열 구하기 문제다.
-
세그먼트 트리를 이용하는 방식과 이분탐색으로 푸는 방식이 있다.
세그먼트 트리를 이용하는 방식
-
먼저 값들을 인덱스와 함께 pair로 저장 후, 값을 기준으로 정렬해준다.
-
정렬된 값의 인덱스로 이동 후, 0부터 해당 인덱스까지의 제일 긴 증가하는 부분수열 값에 +1을 해준후 해당 인덱스와 부모값들까지 갱신해준다.
-
정렬이 이미 되어있는 상태이므로
0부터 현재 값의 인덱스까지의 제일 긴 증가하는 부분수열값은
자기값보다 작은 값들의 제일 긴 증가하는 부분수열값과 같으므로
해당 값에 +1을 더해서 저장하는 원리다.void Solution() { int tmp = 0,result=0; //이미 값으로 정렬된 벡터를 순회 for (auto iter : v) { //0부터 현재 값의 인덱스까지의 구간의 제일 긴 증가하는 부분수열에 +1을 해준다. tmp = FindLongestIncreasingSubsequence(0, iter.second, 1, 0, firstLeafNodeIdx - 1)+1; //현재값의 인덱스값에 저장 segTree[firstLeafNodeIdx + iter.second] = tmp; //지금까지 구한 제일 긴 증가하는 부분수열의 최대값을 result에 저장해줌. result = max(tmp, result); //현재 값의 인덱스의 조상노드들도 갱신해준다. SetAncestorNode(firstLeafNodeIdx + iter.second); } cout << N-result; }
이분탐색을 이용한 방식
-
처음 주어진 입력값을 순회하며 벡터가 비어있거나
벡터의 back()값보다 현재값이 크면 벡터에 push_back을 한다. -
벡터의 back()값보다 현재값이 작으면
벡터에서 현재값보다 큰 원소중 제일 작은 값을
이분탐색을 이용해 찾아 해당 값을 현재값으로 교체한다. -
벡터의 사이즈가 제일 긴 증가하는 부분수열이다.
for (int i = 0; i < N; i++) {
cin >> tmp;
if (i == 0 || v.back() < tmp) v.push_back(tmp);
else {
tmpIdx = BinarySearch(tmp);
v[tmpIdx] = tmp;
}
}
cout << N - v.size();세그먼트 트리를 이용한 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N,firstLeafNodeIdx=1;
int segTree[262144];
vector<pair<int, int>> v;
//목표구간 [targetL,targetR]의 제일 긴 증가하는 부분수열값 찾는 재귀함수. 현재구간 [curL,curR]을 기준으로 찾아간다
int FindLongestIncreasingSubsequence(int targetL, int targetR, int nodeNum, int curL, int curR) {
if (targetR < curL || curR < targetL) return 0;
if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
int mid = (curL + curR) / 2;
return max(FindLongestIncreasingSubsequence(targetL, targetR, nodeNum * 2, curL, mid),
FindLongestIncreasingSubsequence(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR));
}
//idx의 조상노드들 전부 갱신해주는 함수
void SetAncestorNode(int idx) {
while (idx > 1) {
idx /= 2;
segTree[idx] = max(segTree[idx * 2], segTree[idx * 2 + 1]);
}
}
void Solution() {
int tmp = 0,result=0;
//이미 값으로 정렬된 벡터를 순회
for (auto iter : v) {
//0부터 현재 값의 인덱스까지의 구간의 제일 긴 증가하는 부분수열에 +1을 해준다.
tmp = FindLongestIncreasingSubsequence(0, iter.second, 1, 0, firstLeafNodeIdx - 1)+1;
//현재값의 인덱스값에 저장
segTree[firstLeafNodeIdx + iter.second] = tmp;
//지금까지 구한 제일 긴 증가하는 부분수열의 최대값을 result에 저장해줌.
result = max(tmp, result);
//현재 값의 인덱스의 조상노드들도 갱신해준다.
SetAncestorNode(firstLeafNodeIdx + iter.second);
}
cout << N-result;
}
void Input() {
int tmp = 0;
cin >> N;
while (firstLeafNodeIdx < N) firstLeafNodeIdx *= 2;
for (int i = 0; i < N; i++) {
cin >> tmp;
v.push_back({ tmp,i });
}
//이문제에선 각 값이 겹치진 않으므로 따로 comp함수 안 짜도 됨.
sort(v.begin(), v.end());
Solution();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}이분탐색을 이용한 코드
#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
int BinarySearch(int elem) {
int low = 0, high = v.size() - 1, mid = 0;
//벡터내의 제일 작은값보다 작으면 바로 작은값 리턴
if (v[low] >= elem)
return low;
//elem값보다 크거나 같은 값이 high, elem값보다 작은 값이 low에 저장됨
while (low+1 < high) {
mid = (low + high) / 2;
if (v[mid] < elem) low = mid;
else high = mid;
}
return high;
}
void Input() {
int N=0,tmp=0,tmpIdx=0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> tmp;
if (i == 0 || v.back() < tmp) v.push_back(tmp);
else {
tmpIdx = BinarySearch(tmp);
v[tmpIdx] = tmp;
}
}
cout << N - v.size();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}
문풀후생
계속 풀어왔던 LIS구하기 문제여서 어려울건 없었다.
코딩 창고!