[BOJ/Gold 3] 백준 2550 전구(C++)

문제 링크

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

 

 

문제

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.

 

 

하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.

위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이 누르면 전선이 만나는 1번과 5번 전구는 켜지지 않지만 3번 전구는 켜지게 된다.

여러분이 할 일은 가장 많은 전구가 켜지도록 스위치를 누르는 것이다. 위 그림에서는 3번과 4번 그리고 5번 스위치를 누르는 경우와 1번과 3번 그리고 4번을 누르는 경우에 세 개의 전구가 켜지게 되고, 이 두 가지 경우가 가장 많은 전구가 켜지는 경우이다.

스위치의 번호순서와 전구의 번호순서가 주어질 때, 어떤 스위치를 누르면 가장 많은 전구가 켜지는지를 알아내는 프로그램을 작성하시오.

 

입력

첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.

 

출력

첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다. 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

 

예제 입력 1

5
2 4 1 5 3
4 5 1 3 2

예제 출력 1

3
3 4 5

 

알고리즘 분류

• 다이나믹 프로그래밍
• 이분 탐색

 

풀이

스위치와 전구가 연결되어 있으므로, 스위치의 순서대로 나열된 연결된 전구의 위치 배열을 구한다.

예제에서의 전구의 위치 배열은 5 1 3 2 4이다.

이 전구의 위치 배열의 가장 긴 증가하는 부분 수열을 구한다.

근데 우리가 구하는 것은 켜야 하는 스위치의 개수 및 종류이다. 전구의 위치 배열로 스위치 번호를 구할 수 있으므로, 가장 긴 증가하는 부분 전구의 위치 배열을 통해서 스위치의 종류를 구한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#define MAX 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int Switches[MAX], Bulbs[MAX];
unordered_map<int, int> UM;
vector<int> Numbers;
vector<int> Answer;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Switches[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> Bulbs[i];
		UM.insert(make_pair(Bulbs[i], i));
	}
}

vector<int> findSwitches() {
	vector<int> Result;
	vector<int> DP;
	vector<int> Indices;
	vector<int> PrevIndices(N, -1);

	for (int i = 0; i < N; i++) {
		auto it = lower_bound(DP.begin(), DP.end(), Numbers[i]);
		int Index = it - DP.begin();

		if (it == DP.end()) {
			DP.push_back(Numbers[i]);
			Indices.push_back(i);
		}
		else {
			*it = Numbers[i];
			Indices[Index] = i;
		}

		if (Index > 0) {
			PrevIndices[i] = Indices[Index - 1];
		}
	}

	int Current = Indices.back();
	while (Current != -1) {
		Result.push_back(Bulbs[Numbers[Current]]);
		Current = PrevIndices[Current];
	};

	sort(Result.begin(), Result.end());

	return Result;
}

void settings() {
	for (int i = 0; i < N; i++) {
		Numbers.push_back(UM[Switches[i]]);
	}
	Answer = findSwitches();
}

void printAnswer() {
	cout << (int)Answer.size() << "\n";
	for (int i = 0; i < (int)Answer.size(); i++) {
		cout << Answer[i] << " ";
	}
	cout << "\n";
}

int main() {
    FASTIO

	input();
	settings();
    printAnswer();

    return 0;
}