백준1365(꼬인 전깃줄)

jh Seo·2023년 4월 11일

백준 세그먼트 트리 이분탐색 한번에 푼 문제

백준

목록 보기

148/194

개요

백준 1365번: 꼬인 전깃줄

입력
첫 줄에 전봇대의 개수 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();
}