[BOJ] 2759 팬케익 뒤집기

문제 링크

 

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

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

팬케이크의 갯수가 최대 30개, 그리고 뒤집을 수 있는 최대 횟수가 2n-3번, 즉 57번이므로 완전탐색으로는 답을 구할 수 없었다. 대신 팬케이크를 차례대로 맞춰가는 방법을 생각했다. 위에서부터 k번째까지 뒤집을 수 있으므로, 아래쪽부터 맞춰가기로 했다.

 

1. i를 팬케이크의 갯수 num부터 2까지 1씩 줄여간다.

2. 팬케이크가 순서대로 쌓여있는지 확인한다. 순서대로 쌓여있으면 loop 종료

3. 현재 제일 위에 있는 팬케익이 i가 아닐 경우 i가 있는 곳까지 뒤집기 -> 맨 위의 팬케익이 i가 된다.
4. 위에서부터 i까지 뒤집기 -> 위에서부터 i번째에 i번째 팬케익이 위치하게 된다.

이 방법을 사용하면 팬케이크를 차례대로 쌓을 수 있지만 뒤집는 횟수가 최소가 아니므로, 뒤집는 횟수를 최소로 하기 위해서는 다른 방법을 사용해야 할 것 같다.

 

전체 코드는 아래와 같다.

int main() {
	int i, j, n, num, k;
	cin >> n;
	while (n--) {
		vector<int> vec;
		cin >> num;
		for (i = 0; i < num; i++) {
			cin >> k;
			vec.push_back(k);
		}

		///////////////////////////////////////////////////////////////////////////////////////
		//1. i <- num to 2, 아래에서부터 차례대로 맞춰간다.
		//2. 현재 제일 위에 있는 팬케익이 i가 아닐 경우
		//   i가 있는 곳까지 reverse -> 맨 위의 팬케익이 i가 된다.
		//3. 위에서부터 i까지 reverse -> 위에서부터 i번째에 i번째 팬케익이 위치하게 된다.
		///////////////////////////////////////////////////////////////////////////////////////

		vector<int> ret;
		for (i = num; i > 1; i--) {
			for (j = 0; j < num - 1; j++) { // 순서대로 쌓여있는지 체크
				if (vec[j] + 1 != vec[j + 1]) break;
			}
			if (j == num - 1) break;
			if (vec[0] != i) {
				for (j = 0; j < num; j++) {
					if (vec[j] == i) {
						ret.push_back(j + 1);
						reverse(vec.begin(), vec.begin() + j + 1);
						break;
					}
				}
			}
			ret.push_back(i);
			reverse(vec.begin(), vec.begin() + i);
		}
		cout << ret.size() << " ";
		for (auto it : ret) cout << it << " ";
		cout << "\n";
	}
}