[BOJ 24621 // C++] Photoshoot 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24621번 문제인 Photoshoot 2이다.
문제는 아래 링크를 확인하자.

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

24621번: Photoshoot 2

소의 이동은 오른쪽에서 왼쪽으로만 가능하므로, 모든 이동을 마친 뒤 가장 오른쪽에 있어야 하는 소보다 오른쪽에 있는 소는 모두 왼쪽으로 이동하는 과정을 거쳐야 함을 관찰하자.

 

위의 관찰에 이어서, 모든 이동을 마친 뒤 두번째로 오른쪽에 있어야 하는 소는 (1) 앞선 단계에서 왼쪽으로 이동되었거나 (2) 그렇지 않은 두 가지 경우중 하나에 속함을 관찰하자. 이 때, (1)에 해당한다면 그 이동을 적절하게 해 소의 순서를 맞출 수 있을 것이고, (2)에 해당한다면 첫 단계와 같이 해당 소의 오른쪽에 남아있는 첫번째 소가 아닌 아직 이동하지 않은 소를 이동시키는 과정을 거쳐야 함을 알 수 있다.

 

위와 같은 과정을 반복하는 것으로 문제를 해결하자. 즉, 주어진 두 배치를 오른쪽 끝부터 읽어나가면서 각 소가 앞선 단계에서 이동되었는지를 체크하고 안 이동되었다면 배치할 소의 오른쪽에 있는 소를 모두 이동시키는 작업을 반복해 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

int N;
vector<int> vec1, vec2;
bool visited[100001];
int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		vec1.emplace_back(x);
	}
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		vec2.emplace_back(x);
	}

	while (!vec2.empty()) {
		int cur = vec2.back(); vec2.pop_back();
		if (visited[cur]) continue;
		while (vec1.back() != cur) {
			visited[vec1.back()] = 1, ans++;
			vec1.pop_back();
		}
		vec1.pop_back();
	}

	cout << ans;
}