# [Gold III] 상범 마법 팬케이크 하우스 [문제 링크](https://www.acmicpc.net/problem/2715) ## 문제 설명 <p> 상범 마법 팬케이크 하우스의 요리사는 가끔씩 팬케이크를 만들다가 잠에 빠진다. 그래서 쌓아둔 팬케이크의 한쪽이 종종 타버린다. 명백하게 탄 팬케이크를 서빙하는 건 좋은 생각이 아니다. 서빙하기 전에 웨이트리스는 팬케이크 더미를 배치해서 타버린 쪽이 아래를 향하도록 할 것이다. 또, 가장 위에는 크기가 제일 작은 팬케이크를, 가장 아래에는 크기가 제일 큰 팬케이크를 놓아 크기 순으로 정렬을 하려고 한다. 웨이트리스를 도와 올바르게 팬케이크를 쌓는 프로그램을 작성하시오.</p> <p> 우리는 한쪽면이 타버린 N개의 팬케이크 더미를 뒤집어야 한다. 우리가 위에서부터 k개의 팬케이크를 하나의 단위로 뒤집으면 맨 위에 있던 팬케이크는 k번째로 들어가고, k번째에 있던 팬케이크는 맨 위로 올라오게 된다.</p> <p> 예를 들면 다음과 같다.(+는 바닥이 탄 것, -는 위가 탄 것, 숫자는 팬케이크의 크기)</p> <p> +1 -3 -2 [flip 2] => +3 -1 -2 [flip 1] => -3 -1 -2 [flip 3] => +2 +1 +3 [flip 1] => -2 +1 +3 [flip 2] => -1 +2 +3 [flip 1] => +1 +2 +3</p> <p> 최대 3n-2 번의 뒤집기(flip)한 수열을 찾는 프로그램을 만들어야 한다.</p> <p> (수열의 처음과 마지막은 처음 주어진 상태와 아래가 모두 탄 팬케이크로 만든 상태가 된다)</p> ## 입력 <p> 첫 줄에 테스트 케이스의 수 N이 입력으로 들어온다. 다음 N줄에는 각각의 줄에 팬케이크 수 M, 과 팬케이크의 크기(1~M)이 섞인 순서로 +또는 -부호를 달고 한번씩 등장한다. (M ≤ 30)</p> ## 출력 <p> 각각의 케이스에 대해 한 줄씩 출력한다. 뒤집는 횟수 K(≥0), 한 번에 뒤집어야 하는 케이크 더미의 수 K개를 공백으로 구분하여 출력한다. 하나의 케이스에 대해 여러 개의 답이 존재할 수 있다. (예로 든 문제에서 3 2 3 또한 답이 될 수 있다.)</p> ## 풀이 M부터 1까지 순서대로 i번 팬케이크를 첫번째로 올리고, -를 붙인 후에, 다시 i번째로 보내면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int state[30]; void flip(int idx) { for(int i=0;i<idx/2;i++) swap(state[i], state[idx-1-i]); for(int i=0;i<idx;i++) state[i]*=-1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(n--) { int m; cin >> m; for(int i=0;i<m;i++) cin >> state[i]; vector<int> res; for(int i=m;i>=1;i--) { int idx=0; for(int j=0;j<i;j++) { if(abs(state[j])==i) idx=j; } if(idx==i-1 && state[idx]==i) continue; if(idx) { res.push_back(idx+1); flip(idx+1); } if(state[0]>0) { res.push_back(1); state[0]*=-1; } res.push_back(i); flip(i); } cout << res.size(); for(int e:res) cout << ' ' << e; cout << '\n'; } } ```