Stacks Of Flapjacks/이동현

소감 ¶

간단할듯 하여 도전했는데 역시;;
해법은 일단 0~n 까지 케익 중 가장 큰 케익 바로뒤에 주걱을 꼽고 한번 뒤집어 가장 큰 케익을 맨 위에 오게한 후 다시 flip(1)로 뒤집어 가장 큰 케익이 맨 아래 n에 오게한다.
그 다음엔 0~n-1 까지 케익을 가지고 동일한 동작을 반복하고.. 이렇게 최고 n번정도만 하면 팬케익이 작은것부터 큰것까지 정렬된다.

시간 대부분을 입력받는것 짜는데 매달렸으나 아직도 입력부분을 문제에서 요구한대로 완성하지 못했다.
여러줄 입력받는걸 만들기 힘들어 일단 그냥 한줄 입력받고 결과출력 하는 식으로 했다.

[edit]

코드 ¶

~cpp 
//Stacks Of Flapjacks:2005.04.15 이동현
#include <iostream>
using namespace std;

class StacksOfFlapjacks{
private:
	int* cake;	//케이크들
	int arr_size;	//케익 개수
	void flip(int n){	//n번에다가 주걱 넣고 뒤집어!
		int k = (arr_size-n+1)/2;
		for(int i=0; i<k; i++){
			swap(cake[i],cake[arr_size-n-i]);
		}
		cout << n << " ";
	}
	int searchBigIndex(int end){	//0~end index까지 검사하여 가장 큰 수의 index리턴.
		int big_index=0;
		for(int i=1;i<=end;i++){
			if(cake[big_index]<cake[i])
				big_index = i;
		}
		return big_index;
	}
	bool isEnd(){	//모든숫자가 정렬되었는지 확인.
		for(int i=1;i<arr_size;i++){
			if(cake[i-1]>cake[i])
				return false;
		}
		cout << "0\n";	//모든케익이 정렬되었으므로 더이상 뒤집을게없다는 0출력
		return true;
	}
public:
	void run(int*arr, int size){	
		cake = arr;
		arr_size = size;
		for(int j=arr_size-1, n=1;j>=0;j--, n++){	
			if(isEnd()==true)
				break;
			if(searchBigIndex(j)==j)	//제일 큰 케익이 놓일자리에 이미 놓여있다면 다음뒤집기로.
				continue;		
			if(searchBigIndex(j)!=0)	//맨위에 제일큰케익이 있으면 뒤집을 필요가 없다.
				flip(arr_size-searchBigIndex(j));
			flip(n);			
		}		
	}
};

int main(void){	
	StacksOfFlapjacks sof;
	int arr[30],j=0;	
	while(cin >> arr[j]){	//입력의 끝은 ^Z(EOF)를 흉내내서 종료.				
		j++;
                  if(j>30) break;
	}
	for(int i=0;i<j;i++)
		cout << arr[i] << " ";
	cout << "\n";
	sof.run(arr,j);		
	for(i=0;i<j;i++)
		cout << arr[i] << " ";	
	return 0;
}