백준 2550 전구
- https://www.acmicpc.net/problem/2550
- 스위치 연결선이 겹쳐지지 않기 위해선, 오른편의 연결된 스위치의 위치가 증가하는 수열이어야 한다
- 왼편 스위치의 번호 -> sw1[i]에 저장
오른편 스위치의 번호 -> sw2[i]에 저장
sw1[i]와 sw2[i]를 연결했을 때, 오른편의 연결된 스위치의 위치
-> line[i]에 저장
- line[i]의 LIS 배열 구하면서
-> record 배열의 제일 뒤부터 탐색하여
-> record[i]에 저장된 인덱스가 순차적인 내림차순이 되는 경우
-> ret 벡터에 push_back(sw2[line[i]]) 연산을 한다
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int sw1[10000] = { 0 };
int sw2[10000] = { 0 };
int line[10000] = { 0 };
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> sw1[i];
for (int i = 0; i < n; i++) cin >> sw2[i];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (sw1[i] == sw2[j])
line[i] = j;
vector <int> vt;
vector <int> record;
vector <int> ret;
int idx = 0;
vt.push_back(line[0]);
record.push_back(0);
for (int i = 1; i < n; i++) {
if (vt.back() < line[i]) {
vt.push_back(line[i]);
record.push_back(++idx);
}
else {
auto it = lower_bound(vt.begin(), vt.end(), line[i]);
*it = line[i];
record.push_back(it - vt.begin());
}
}
int flag = idx;
for (int i = n - 1; i >= 0; i--) {
if (record[i] == flag) {
ret.push_back(sw2[line[i]]);
flag--;
}
if (flag == -1)
break;
}
sort(ret.begin(), ret.end());
cout <<idx + 1<< "\n";
for (auto it = ret.begin(); it != ret.end(); it++)
cout << *it << " ";
return 0;
}
📌참고 자료