백준 2568 전깃줄 -2 (c++) : 피너클

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

2568번: 전깃줄 - 2

lcs문제다.

아래그림을

위에 처럼 만들면 된다. 오른쪽을 보면 1, 4, 6, 7, 10으로 게속해서 증가하는걸 알수있다.

부분수열중 증가하는 부분수열을 찾으면 되는 문제다.

int n;
vector<pair<int, int>> v;
vector<int> lis, back(100001, 0);
vector<int> ::iterator it;

 

사용하는 변수다. 

v는 입력받을때, lis는 수열을 담을 배열, back은 백트래킹 할때, it은 이진탐색을 쓸때 사용할것이다.

cin >> n;
v.push_back({ -1, -1 });
for (int i = 1; i <= n; i++) {
	int a, b;
	cin >> a >> b;
	v.push_back({ a, b });
}
sort(v.begin(), v.end());

값을 입력받은 다음 v를 정렬한다. v에 {-1, -1}을 넣은 이유는 배열의 시작을 0이 아닌 1로 하기 위해서다.

int idx = 1;
for (int i = 1; i <= n; i++) {
	if (lis.empty()) {
		lis.push_back(v[i].second);
		back[i] = idx++;
	}
	else if (lis.back() < v[i].second) {
		lis.push_back(v[i].second);
		back[i] = idx++;
	}

그후 1부터 n까지 반복하며 lis를 업데이트한다.

만약 lis가 비어있거나 lis의 마지막이 v[i].second보다 작다면

lis에 v[i].second값을 넣고 back[i]=idx++를 한다.

	else {
		it = lower_bound(lis.begin(), lis.end(), v[i].second);
		lis[it - lis.begin()] = v[i].second;
		back[i] = (it - lis.begin() + 1);
	}
}

둘다 아니라면 v[i].second가 들어가야할 위치를 이진탐색을 이용해 찾는다.

it에 위치를 담은 후 lis[it - lis.begin()]에 v[i].second값을 넣어준다.

그후 back[i]에는 it - lis.begin() + 1을 넣어준다. +1을 하는 이유는 it이 lis.begin() 일경우 0이 될수도 있기 때문이다.

cout << n - lis.size() << '\n';
backtrack(lis.size(), n);

그후 n에서 lis의 크기를 뺸 값을 출력한뒤 백트래킹을 한다.

이번 백트래킹에서는 부분 수열을 출력하는 것이 아닌 부분 수열이 아닌것을 출력해야한다.

void backtrack(int num, int idx) {
	if (idx == 0) return;
	if (back[idx] == num) {
		backtrack(num - 1, idx - 1);
	}
	else {
		backtrack(num, idx - 1);
		cout << v[idx].first << '\n';
	}
}

만약 idx가 0이라면 함수를 종료시킨다.

만약 back[idx] == num이라면 부분수열에 포함됬다는 뜻이다.

그대로 backtrack(num - 1, idx - 1)을 실행한다.

만약 다르다면 포함되어있지 않다는 뜻이다.

backtrack(num, idx - 1)을 한뒤 v[idx].first를 출력한다. 출력을 먼저하면 답이 거꾸로 출력될것이다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<pair<int, int>> v;
vector<int> lis, back(100001, 0);
vector<int> ::iterator it;

void backtrack(int num, int idx) {
	if (idx == 0) return;
	if (back[idx] == num) {
		backtrack(num - 1, idx - 1);
	}
	else {
		backtrack(num, idx - 1);
		cout << v[idx].first << '\n';
	}
}

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

	cin >> n;
	v.push_back({ -1, -1 });
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a, b });
	}
	sort(v.begin(), v.end());

	int idx = 1;
	for (int i = 1; i <= n; i++) {
		if (lis.empty()) {
			lis.push_back(v[i].second);
			back[i] = idx++;
		}
		else if (lis.back() < v[i].second) {
			lis.push_back(v[i].second);
			back[i] = idx++;
		}
		else {
			it = lower_bound(lis.begin(), lis.end(), v[i].second);
			lis[it - lis.begin()] = v[i].second;
			back[i] = (it - lis.begin() + 1);
		}
	}
	cout << n - lis.size() << '\n';
	backtrack(lis.size(), n);
}

전체코드다.