[문제해결기법]pancake2

pancake1과 달리 집게가 없으므로 주걱만 이용해야한다.

1. pancake의 크기를 모두 입력받고 오름차순으로 sorting해 right_order vector에 저장한다.

2. right_order의 마지막과 pancake의 마지막을 비교한다.

3. 만약 같지 않으면

  3-1 pancake에서 같지 않은 수(임의로 x라 한다) x를 찾는다

  3-2 만약 x가 첫번째에 있다면 x가 들어가야할 자리부터 처음까지 뒤집는다.

  3-3 만약 x가 첫번째에 있지 않다면 x를 첫 번째로 가도록 뒤집은 다음 3-1을 진행한다.

       (이 경우에는 count를 2번 진행한다.)

4. right_order와 pancake이 모두 같다면 while문을 빠져나온다.

#include <iostream> #include <fstream> #include <algorithm> #include <vector> using namespace std; vector<int> pancake; int change_pancake(int change_count, int index, vector<int>&right_order) { int flag = 1; while (flag) { while (right_order[index] == pancake[index]) { index--; if (index < 0) { flag = 0; break; } } if (!flag) break; change_count++; vector<int>::iterator iter; iter = find(pancake.begin(), pancake.end(), right_order[index]); if (iter == pancake.begin()) reverse(pancake.begin(), pancake.begin() + index + 1); else reverse(pancake.begin(), iter + 1); } return change_count; } int main() { ifstream fcin; fcin.open("fancake2_input.txt"); ifstream fcout; fcout.open("fancake2_output.txt"); int for_count; fcin >> for_count; while (for_count--) { pancake.clear(); int pancake_count, number; fcin >> pancake_count; while (pancake_count--) { fcin >> number; pancake.push_back(number); } reverse(pancake.begin(), pancake.end()); vector<int> right_order(pancake.size()); copy(pancake.begin(), pancake.end(), right_order.begin()); sort(right_order.begin(), right_order.end()); int answer; fcout >> answer; if (answer != change_pancake(0, pancake.size() - 1, right_order)) { cout << "WRONG : " << for_count << "번 째" << endl; break; } } cout << "PERFECT!!" << endl; system("pause"); }