[BOJ 2759 // C++] 팬케이크 뒤집기

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

 

이번에 볼 문제는 백준 2759번 문제인 팬케이크 뒤집기이다.
문제는 아래 링크를 확인하자.

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

2759번: 팬케이크 뒤집기

"정렬된 위치에 있지 않은 가장 큰 팬케이크"를 맨 위로 오게끔 한번 뒤집고 그 팬케이크가 정렬된 위치에 가게끔 한번 뒤집는 것을 반복하는 것으로 팬케이크들을 올바른 상태로 정렬시킬 수 있다.

 

위와 같은 방법으로 N개의 팬케이크를 정렬시키면 많아야 2N번으로 정렬시킬 수 있음을 관찰하자. 추가로, "정렬된 위치에 있지 않은 가장 큰 팬케이크"가 2이면 팬케이크를 한번 뒤집는 것으로도 충분히 정상 위치로 보낼 수 있다는 점과 "정렬된 위치에 있지 않은 가장 큰 팬케이크"가 1이 될 수 없음을 관찰하자. 이 두 가지 관찰을 이용하면 주어지는 팬케이크의 정렬을 항상 2N-3(단, N>1)회 이하의 뒤집기를 이용하여 완료할 수 있음을 알 수 있다.

 

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

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

int T, N;
int arr[31];

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

	cin >> T;
	while (T--) {
		vector<int> ans;
		cin >> N;
		for (int i = 1; i <= N; i++) cin >> arr[i];
		for (int n = N; n > 1; n--) {
			for (int i = 2; i < n; i++) {
				if (arr[i] == n) {
					ans.emplace_back(i);
					int L = 1, R = i;
					while (L < R) swap(arr[L++], arr[R--]);
					break;
				}
			}
			if (arr[n] != n) {
				ans.emplace_back(n);
				int L = 1, R = n;
				while (L < R) swap(arr[L++], arr[R--]);
			}
		}

		cout << ans.size();
		for (auto& x : ans) cout << ' ' << x;
		cout << '\n';
	}
}