취미로 코딩하기

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

이번에 볼 문제는 백준 22887번 문제인 Reversort Engineering이다.
문제는 아래 링크를 확인하자.

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

먼저, 마지막 원소를 제외한 각 원소에 대하여 적어도 길이 1의 배열에 대한 Reverse 연산을 진행해야함을 확인하자. 따라서 총 $N-1$단계를 진행한다는 점을 이용하면 $C$의 값이 $N-1$ 이상이어야 함을 알 수 있다.

또한 마지막 원소를 제외한 각 원소에 대하여 가장 오른쪽 원소까지 뒤집는 연산을 해야 하는 경우가 비용이 가장 큰 경우가 될 것이다. 따라서 $C$ 값이 $N(N+1)/2-1$ 이하여야 함을 알 수 있다.

reversort의 과정을 역으로 뒤집어 생각해보자. 각 단계에서, 길이 $k$의 부분배열을 뒤집어 정렬된 위치로 이동하게 되는 "가장 작은 원소"의 이동거리를 원하는 대로 설정할 수 있음을 관찰하면, 이를 이용해 (불가능한 경우가 아닌) 임의의 $C$에 대하여 문제의 답이 되는 배열을 구성하는 알고리즘을 설계하는 것은 어렵지 않을 것이다.

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

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

int N, C;
vector<int> vec;
vector<int> ans;

void solve() {
	vec.clear(), ans.clear();
	cin >> N >> C; 
	if (C < N - 1) {
		cout << "IMPOSSIBLE\n";
		return;
	}
	
	C -= N - 1;
	for (int i = 1; i < N; i++) {
		int val = min(C, i);
		vec.emplace_back(val + 1);
		C -= val;
	}
	
	if (C) {
		cout << "IMPOSSIBLE\n";
		return;
	}

	for (int i = 1; i <= N; i++) ans.emplace_back(i);
	for (int i = 0, L = N - 2; i + 1 < N; i++, L--) {
		int LL = L, RR = L + vec[i] - 1;
		while (LL < RR) {
			swap(ans[LL], ans[RR]);
			LL++, RR--;
		}
	}
	for (auto &x : ans) cout << x << ' ';
	cout << '\n';
}

int T;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}

BOJ Random Defense #9