18239 편안한 수열 만들기 (골드 3)

이번 문제는 애드 훅이 주제인 문제이다.

 

애드 훅이란 뚜렷한 알고리즘이 없는 문제를 말한다.

결국 그냥 어떤 알고리즘을 응용하는 게 아닌 이 문제만의 풀이가 있다는 뜻이다.

 

 

 

우선 문제 설명을 하자면 입력으로는 N과 K가 주어진다.

1~N까지의 배열이 존재하는데 뒤쪽 K개의 수를 앞으로 이동시켰을 때,

swap과 reverse를 이용해 정확히 5번만에 원래대로 수열을 되돌려 놓을 수 있는지, 그리고 그 방법을 출력하는 문제이다.

N = 7, K = 3

 

 

4가지의 예외 상황을 제외하고는 모두 같은 풀이로 풀 수 있다.

 

같은 풀이도 여러가지가 있는데 내가 찾은 건 두 가지 방법이다.

1. 바뀐 수열에서 reverse 1 K, reverse K+1 N, reverse 1 N(여기까지 하면 오름차순 정렬), reverse 1 N, reverse 1 N

2. 바뀐 수열에서 reverse 1 N, reverse 1 N-K, reverse N-K+1 N(여기까지 하면 오름차순 정렬), reverse 1 N, reverse 1 N

 

4가지의 예외 상황은 

1. N == 2

2. N == 3

3. 1,2 상황을 제외하고 K == 1

4. 1,2 상황을 제외하고 K == N - 1

 

 

1의 경우는 그냥 swap 1 2를 5번 해주면 된다.

3의 경우는 swap 1 2, swap 2 N, reverse 2 N-1, reverse 1 N, reverse 1 N

 

4의 경우는 3의 경우와 반대로 해주면 된다.'

 

 

2의 경우는 1 2 3 이 되는 경우가 없으므로 NO인데 이는 밑의 표로 입증가능하다. 

(이건 스터디 하면서 배움..)

 

// 편안한 수열 만들기 (골드 3)
#include <iostream>

using namespace std;

int N, K;

int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> K;

	// 2~3
	if (N == 2) { // K = 1
		cout << "YES" << '\n'; // ( 2 1 )  1 2    2 1   1 2    2 1   1 2
		cout << "reverse " << 1 << " " << 2 << '\n';
		cout << "reverse " << 1 << " " << 2 << '\n';
		cout << "reverse " << 1 << " " << 2 << '\n';
		cout << "reverse " << 1 << " " << 2 << '\n';
		cout << "reverse " << 1 << " " << 2 << '\n';

		return 0;
	}
	else if (N == 3) {
		cout << "NO";
        
		return 0;

	}


	// 4~
	if (K == 1) {
		cout << "YES" << '\n';
		cout << "swap " << 1 << " " << 2 << '\n';
		cout << "reverse " << 2 << " " << N << '\n';
		cout << "reverse " << 2 << " " << N - 1 << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
	}
	else if (K == N - 1) {
		cout << "YES" << '\n';
		cout << "swap " << N - 1 << " " << N << '\n';
		cout << "reverse " << 1 << " " << N - 1 << '\n';
		cout << "reverse " << 2 << " " << N - 1 << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
	}
	else
	{
		cout << "YES" << '\n';
		cout << "reverse " << 1 << " " << K << '\n';
		cout << "reverse " << K + 1 << " " << N << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
		cout << "reverse " << 1 << " " << N << '\n';
	}

	return 0;
}
// 2020KB, 0ms

 

 

#include <iostream>

using namespace std;

int N, K;

int main() {
	cin >> N >> K;


	if (N == 3) {
		cout << "NO";
		return 0;
	}

	if (N == 2) {
		cout << "YES" << '\n';
		cout << "swap " << 1 << ' ' << 2 << '\n';
		cout << "swap " << 1 << ' ' << 2 << '\n';
		cout << "swap " << 1 << ' ' << 2 << '\n';
		cout << "swap " << 1 << ' ' << 2 << '\n';
		cout << "swap " << 1 << ' ' << 2 << '\n';

		return 0;
	}

	if (K == 1) {
		cout << "YES" << '\n';
		cout << "swap " << 1 << ' ' << 2 << '\n';
		cout << "reverse " << 2 << ' ' << N << '\n';
		cout << "reverse " << 2 << ' ' << N - 1 << '\n';
		cout << "reverse " << 1 << ' ' << N << '\n';
		cout << "reverse " << 1 << ' ' << N << '\n';

	}
	else if (K == N - 1) {   
		cout << "YES" << '\n';
		cout << "swap " << N - 1 << ' ' << N << '\n'; 
		cout << "reverse " << 1 << ' ' << N - 1 << '\n'; 
		cout << "reverse " << 2 << ' ' << N - 1 << '\n'; 
		cout << "reverse " << 1 << ' ' << N << '\n'; 
		cout << "reverse " << 1 << ' ' << N << '\n';

	}
	else {
		cout << "YES" << '\n';
		cout << "reverse " << 1 << ' ' << N << '\n';
		cout << "reverse " << 1 << ' ' << N - K << '\n';
		cout << "reverse " << N - K + 1 << ' ' << N << '\n';
		cout << "reverse " << 1 << ' ' << N << '\n';
		cout << "reverse " << 1 << ' ' << N << '\n';
	}

	return 0;
}

// 2020 KB, 0ms