[백준] 1365-꼬인 전깃줄(C++)

문제링크: https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

최장 공통 수열 (LCS)를 도출하는 문제.

 

문제에 대한 설명은.... https://yhwan.tistory.com/18

[백준] 1365번: 꼬인 전깃줄 - C++

이분보다 잘할 자신이 없어서 이분꺼 참고

 

 

같은 논리로 작성하였는데, 정작 나는 이분탐색을 사용하지 않은 일반구현으로 제작했다.

아직까지 굳이 이분탐색으로 작성해야하는 이유를 못느끼고 있다.. (문제 검색에 올려놓음)

 

접근방식

 

1.  LCS 만큼의 전깃줄이 남아있을 수 있겠구나

2.  수의 범위가 커서 dp를 사용한 방식O(n^2)으로는 불가능 하겠구나 

 

 

문제풀이 

 

1.  일반적인 구현방식으로 해결

 

정답코드입니다.

아래 방식이 이분탐색을 사용하지 않아서 문제가 될 수 있을 것 같은데, 아직까지는 잘 모르겠습니다.

혹시 아시는 분은 댓글 부탁드립니다. 

 

 

--- ++ 추가 ---

아래방식은 해당 문제에서는 시간초과가 난다. 

최악의 경우에는 취약한 방법이기 때문이다. 따라서 이분탐색 방식을 권장한다.

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

 

단순 구현

#include <iostream>
#include <vector>
using namespace std;

int n = 0, temp;
vector <int> vec;
int lcs[100000];
int lcs_cnt = -1;


void low_bound(int num) {

	int val = vec[num];

	for (int i = 0; i <= lcs_cnt; i++) {
		if (val < lcs[i]) {
			lcs[i] = val;
			break;
		}

	}
}


int main() {

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		vec.push_back(temp);
	}

	for (int i = 0; i < vec.size(); i++) {

		if (lcs_cnt == -1)
			lcs[++lcs_cnt] = vec[i];
		else if (lcs[lcs_cnt] <= vec[i]) 
			lcs[++lcs_cnt] = vec[i];
		else if (lcs[lcs_cnt] > vec[i]) 
			low_bound(i);
		

	}
	
	
	
	cout << n - (lcs_cnt + 1) << endl;

	return 0;
}

이분탐색 적용

#include <iostream>
#include <vector>
using namespace std;

int n;
int arr[1000000];
vector <int> v;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++) {
		if (v.size() == 0 || v[v.size() - 1] < arr[i]) v.push_back(arr[i]);
		else {
			int left = 0;
			int right = v.size();

			while (left <= right) {
				int mid = (left + right) / 2;
				if (v[mid] >= arr[i]) right = mid - 1;
				else left = mid + 1;
			}
			v[left] = arr[i];

		}


	}
	cout << n - v.size() << endl;
	return 0;
}