[백준] 2550 전구

0

백준

목록 보기
132/271
post-thumbnail

백준 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;

	// record 벡터에 line[i]가 vt벡터에 저장되는 위치 저장 
	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());
		}
	}

	// lis 추적
	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;
}

📌참고 자료

profile
Be able to be vulnerable, in search of truth

0개의 댓글